Here is the chunk of code to find the subsets of a set:
Code:voidCode:possibleSubsets(char A[], int N) { for(int i = 0;i < (1 << N); ++i) { for(int j = 0;j < N;++j) if(i & (1 << j)) cout << A[j] << ‘ ‘; cout << endl; } }
Can anybody please explain how this program is working? I mean I am not able to understand how it will produce all the subsets of a set through this logic??
Thanks in advance.
Last edited by anonymous2014; 02-11-2016 at 01:58 AM.
Err. A set has more than one possible subset (if the number of subsets is > 0)
Where did you get this code from? Note that "cout" is C++, not C.
I was reading bit manipulation from Hackerearth's code monk series, there I got this chunk of code.....Ofcourse, it is in c++ but I didnt get how they are generating all the subsets using this logic. Can you please explain the logic?
Rather than explain what this function does, I will explain how you might figure it out yourself.
First, you would put this function in a simple program and test it with a basic test case, such as an array of size 4 with characters 'a' - 'd'. Run the program and look at the output, and see if you can get an idea of the pattern.
Next, you would take out a pencil and paper. Using the values from your basic test case, replace the fixed expressions (e.g. "(1 << N)") with their resulting values. Create a table to keep track of the variables. Then "step through" the code by hand, updating the variables on your table each step of the way. See what the resulting output will be based on the values at each given point.
There's a pretty clear pattern when it's broken down in this way. Hint: It relies on the fact that counting in binary results in all permutations of "on"/"off" within the given range of bits.
