Find All Subsets

One of the standard and useful method of finding the power set is through bit-masking.

Consider a number with N-bits in its binary representation, if we consider that the state of i^th bit depicts whether the i^th array element is included in the current subset or not, then we can uniquely identify one of the subsets (as each number has a different binary representation).

Now we can simply iterate from 1 to 2ⁿ-1, each number in this iteration will define a subset uniquely. To generate the subset just check for the bits that are ON in binary representation on the number, and for each ON bit, we will simply include an array element corresponding to its position.

Remember to not include an empty subset in the final answer.

The steps are as follows :

1. Declare a 2-D container ans to store all the subsets
2. Run a for loop for num from 1 to 2^N -1
3. Run inner for loop for i from 0 to N-1
4. If the i^th bit in num has value equal to 1 then include i^th element of the array in the current subset.
5. Push each subset generated into ans
6. Finally, return ans

Each element has 2 choices, it can either be included or excluded.

Using backtracking we can create all the possible subsets, we can add the current element to the temporary array and make a recursive call for the next element, when the function call returns we remove the current element from the temporary array and again make a recursive call for the next element (standard backtracking approach).

Each time we reach the end of the array, we will add the temporary array to the answer.

The steps are as follows :

1. Initialize a 2D vector ans to store all the subsets
2. Initialize a vector temp to store the current subset
3. Create a recursive function SubsetFinder which takes the following parameters: idx to store current index, temp vector to store current subset, ans 2D vector to store all subsets, arr vector that is the input vector.
4. The initial call is made with idx equal to 0, empty temp vector, empty ans 2D vector, given arr input vector
5. In SubsetFinder we add the idx^th element to temp vector and recursively call SubsetFinder with idx+1 
6. When a function call is returned, we remove the idx^th element from temp, and again recursively call SubsetFinder with idx+1 
7. If the value of idx is equal to size of the input array, add temp to ans
8. Finally, return ans