Given a set of distinct integers, S, return all possible subsets.
Note:
For
example,
If S = [1,2,3],
a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
思路：求集合S的所有组合，就是求n个不同的整数的长度为m（0<=m<=n)的组合，我们把n个整数分成两部分：第一个整数和剩下的所有整数。如果组合包含第一个整数，则下一步在剩余的整数中选取m-1个整数，如果组合里不包含第一个字符，则下一步在剩余的n-1个字符里选取m个字符。这道题很明显使用递归的方式解决。
class Solution { public: void find_subsets(vector<vector<int> > &result,vector<int> &S,vector<int> data,int index) { if(index==S.size()) { result.push_back(data); return; } data.push_back(S[index]); find_subsets(result,S,data,index+1); data.pop_back(); find_subsets(result,S,data,index+1); } vector<vector<int> > subsets(vector<int> &S) { vector<vector<int> > result; result.clear(); vector<int> data; if(S.empty()) return result; sort(S.begin(),S.end()); find_subsets(result,S,data,0); return result; } };
解法二：
class Solution { public: void find_subsets(vector<vector<int> > &result,vector<int> &S,vector<int> data,int index) { result.push_back(data); for(int i=index;i<S.size();i++) { data.push_back(S[i]); find_subsets(result,S,data,i+1); data.pop_back(); } } vector<vector<int> > subsets(vector<int> &S) { vector<vector<int> > result; result.clear(); vector<int> data; if(S.empty()) return result; sort(S.begin(),S.end()); find_subsets(result,S,data,0); return result; } };
原文：http://www.cnblogs.com/awy-blog/p/3659716.html