Subsets I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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],
  []
 ]

代码：

 class Solution {  
 public:  
   void subsetHelper(const vector<int> &S, int start, vector<int> &oneset, vector<vector<int> > &result) {  
     result.push_back(oneset);  
     for (int i = start; i < S.size(); ++i) {  
       oneset.push_back(S[i]);  
       subsetHelper(S, i + 1, oneset, result);  
       oneset.pop_back();  
     }  
   }  
   
   //Version 1: 从树状结构考虑递归方法  
   vector<vector<int> > subsets(vector<int> &S) {  
     vector<vector<int> > result;  
     if (S.empty()) return result;  
     sort(S.begin(), S.end());  
     vector<int> oneset;  
     subsetHelper(S, 0, oneset, result);  
     return result;  
   }  
 };  
   
 // Bitwise solution. each bit has two state, present or not.  
 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;  
   }  
 };  
   
 // iteration  
 class Solution {  
 public:  
   vector<vector<int> > subsets(vector<int> &S) {  
     vector<vector<int> > R;  
     R.push_back(vector<int>());  
     sort(S.begin(), S.end());  
     for (int i = 0; i<S.size(); i++) {  
       int Rsize = R.size();  
       for (int j = 0; j<Rsize; j++) {  
         vector<int> sub(R[j]);  
         sub.push_back(S[i]);  
         R.push_back(sub);  
       }  
     }  
     return R;  
   }  
 };