class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
sort (S.begin(), S.end());
int elem_num = S.size();
int subset_num = pow (2, elem_num);
vector<vector<int> > subset_set (subset_num, vector<int>());
for (int i = 0; i < elem_num; i++)
for (int j = 0; j < subset_num; j++)
if ((j >> i) & 1)
subset_set[j].push_back (S[i]);
return subset_set;
}
};
My solution using bit manipulation


Java codes in a similar way.
public List<List<Integer>> subsets(int[] S) { Arrays.sort(S); int totalNumber = 1 << S.length; List<List<Integer>> collection = new ArrayList<List<Integer>>(totalNumber); for (int i=0; i<totalNumber; i++) { List<Integer> set = new LinkedList<Integer>(); for (int j=0; j<S.length; j++) { if ((i & (1<<j)) != 0) { set.add(S[j]); } } collection.add(set); } return collection; }

This is an amazing solution.Learnt a lot.Let me try to explain this to those who didn't get the logic. Number of subsets for {1 , 2 , 3 } = 2^3 . why ? case possible outcomes for the set of subsets 1 > Take or dont take = 2 2 > Take or dont take = 2 3 > Take or dont take = 2 therefore , total = 2*2*2 = 2^3 = { { } , {1} , {2} , {3} , {1,2} , {1,3} , {2,3} , {1,2,3} } Lets assign bits to each outcome > First bit to 1 , Second bit to 2 and third bit to 3 Take = 1 Dont take = 0 0) 0 0 0 > Dont take 3 , Dont take 2 , Dont take 1 = { } 1) 0 0 1 > Dont take 3 , Dont take 2 , take 1 = {1 } 2) 0 1 0 > Dont take 3 , take 2 , Dont take 1 = { 2 } 3) 0 1 1 > Dont take 3 , take 2 , take 1 = { 1 , 2 } 4) 1 0 0 > take 3 , Dont take 2 , Dont take 1 = { 3 } 5) 1 0 1 > take 3 , Dont take 2 , take 1 = { 1 , 3 } 6) 1 1 0 > take 3 , take 2 , Dont take 1 = { 2 , 3 } 7) 1 1 1 > take 3 , take 2 , take 1 = { 1 , 2 , 3 } In the above logic ,Insert S[i] only if (j>>i)&1 ==true { j E { 0,1,2,3,4,5,6,7 } i = ith element in the input array } element 1 is inserted only into those places where 1st bit of j is 1 if( j >> 0 &1 ) ==> for above above eg. this is true for sl.no.( j )= 1 , 3 , 5 , 7 element 2 is inserted only into those places where 2nd bit of j is 1 if( j >> 1 &1 ) == for above above eg. this is true for sl.no.( j ) = 2 , 3 , 6 , 7 element 3 is inserted only into those places where 3rd bit of j is 1 if( j >> 2 & 1 ) == for above above eg. this is true for sl.no.( j ) = 4 , 5 , 6 , 7 Time complexity : O(n*2^n) , for every input element loop traverses the whole solution set length i.e. 2^n



Amazing solution, it directly captures the intrinsic connection between power set and binary numbers.
When forming a subset, for each element, only 2 possiblities, either it is in the subset or not in the subset, hence we have total number of possible subsets = 2^n.
thinking each element as a bit, it's either on or off when forming the ith subset, and that's the solution!