# My solution using bit manipulation

• ``````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;
}
};``````

• This confuses me at some point.
Would you mind to add some explanation?
That would be helpful and kind. :)

• That should fail if the input S is not sorted.
Mine is accepted and I didn't see any testing case. I don't know if there is any unsorted testing case.

• 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++) {
for (int j=0; j<S.length; j++) {
if ((i & (1<<j)) != 0) {
}
}
}
return collection;
}``````

• Can please explain the logic of code ?

`````` 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]);``````

• what if S.size() > 32?

• `````` 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
``````

• Take data type for j as bitset instead of int.It should solve your problem.

• The code is concise and elegant. However the run time appears not optimal compared to other solution. it's taking N*2^N. I think you can solve it by 2^N.

• Thanks for you explain, cool!, nice work.

• Learned a lot. Code is very neat.

• Actually, @thumike sorting S at the beginning.

• 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!

• ``````int limit = Math.min(N, i + 1);
for (int j = 0; j < limit; j++) {
``````

// add this step between two loops will reduce the time

• Do you need to sort the nums first?

• I think sort is necessary in this case, due to the fact that the original list may not be sorted while the output should be in non-descending order.

• Nice! Elegant! Nice and elegant!

• Thanks for the explanation!

• Thanks a lot! very good code!, Here is python version:

``````def subnets(nums):
nums.sort()
total=2**len(nums)
res=[]*total

for i in range(total):
res.append([])

for i in range(len(nums)):
for j in range(total):
if ((j>>i)&1) >0:
res[j].append(nums[i])
return res
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.