Hello all, Let's begin : Bit masking is used to find all the subsets of an array. In this method, we create a onetoone mapping between all subsets and the natural numbers. Consider the first eight numbers and their binary representation. 0  000 Let's say the contents of the array is {a,b,c} a is at position 1 Consider a subset ac. In this subset, the element at first position of the array is taken. The element at second position is ignored. Again the element at third position is taken. Let's write it as : 101 where 1 at a position indicates the element in the array at that position is taken in the subset. 0 means it is ignored. So, 110 will indicate : element at first and second positions are taken, third one is ignored. So the subset it represents is ab. The array {a,b,c} has three elements. So the number of subsets is 2^3 = 8 Let's write all the subsets in the above mentioned binary notation and let's write the binary numbers in their decimal representation 000  empty set  0 See all the subsets are covered and each subset is identified by a natural number (including 0) from the set [0,2^n1], where n is the size of the array. Now let's come to implementation part : We can iterate through all numbers from 0 to 2^n1 and check which bits are set in the number in its binary form. If a bit is set, we include the element of the array at that position in our present subset. Now, how to check which bit is set? Consider the number 5 (101 in binary). 101 & 001 = 1 (ANDing with 2^0) So,if ANDing with 2^x gives 1, then (x+1)th bit from right (counting starting at 1) is set. C/C++, java gives shift operator (<<) (I don't know about other programming languages). 1<<x means 1 is shifted to the left x times. So, 1<<0 = 001 = 2^0 So, by ANDing the number with 1<<x, where x can be from 0 to n1, we can check which bit is set. Here's the pseudo code to print all the subsets or array (say arr[]) of size (say n).
I hope everything above is understandable. N.B. The complexity of the method is O(2^n * n), as for loop iterates through [0,2^n1] and second loop runs for n times. So this method is extremely slow. For n=20, it takes about a second. Let's say it takes exactly 1 second. Then for n=21, the number of subsets is 2^21, which is 2 times more than when n=20. So for n=21, it will roughly take 2 seconds. Similarly for each increase in the number of elements in the array, the time taken by the code roughly doubles. It will take more than 10 days for n=40. So use it when n<=20. Problems to practice : asked 25 Oct '15, 16:24

@dragonemperor, I think there is a small bug in the pseudo code. The condition in outer for loop would not consider the last integer i.e. the correct code would be answered 08 Jan '17, 16:45
