Solution to LeetCode Problems: Subsets

Subsets

Given a set of distinct integers, S, return all possible subsets.
Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Thoughts:
For a set with n elements, the number of subsets is 2^n. Every element has "chosen" or "not-chosen" state, this led direct use of bit operations.

Solution:

1. class Solution {  
2. public:  
3.     vector<vector<int> > subsets(vector<int> &S) {  
4.         sort(begin(S), end(S)); // ensure non-descending results  
5.           
6.         const size_t n = S.size();  
7.         const size_t num_sets = pow(2, n);  
8.           
9.         vector<vector<int>> ret(num_sets);  
10.       
11.         for(size_t bitwise = 0; bitwise < num_sets; ++bitwise)  
12.         {  
13.             size_t bit_chk = 1;  
14.             for(size_t bit = 0; bit < n; ++bit)  
15.                 if ((bit_chk << bit) & bitwise)  
16.                     ret[bitwise].push_back(S[bit]);  
17.         }  
18.           
19.         return ret;  
20.     }  
21. };