首页 > 代码库 > 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],  []]

 1 class Solution { 2 public: 3     vector<vector<int> > subsets(vector<int> &S) { 4         vector<vector<int>> res; 5         vector<int> empty; 6         res.push_back(empty); 7          8         int len = S.size(); 9         if(len == 0) return res;10         sort(S.begin(),S.end());11         for(int k = 1; k <= len; k++){12             vector<int> path;13             for(int i = 0; i < len; i++)14                 get_subsets(S,res,path,i,k,1);15         }16         return res;17     }18     void get_subsets(vector<int> & S, vector<vector<int>> & res, vector<int> & path, int start,int k, int l){19            path.push_back(S[start]);20            if(l == k) res.push_back(path);21            for(int i = start+1; i < S.size(); i++){22                get_subsets(S,res,path,i,k,l+1);23            }24            path.pop_back();25     }26 };