题目链接
注意点
解法
解法一：递归，每次就将tmp加入ret中，然后往tmp中加一个数字，继续递归。原理如下，第i(i > 0)层表示nums[i-1]的状态(选择或者不选择)，最后叶节点就是结果。
[]
/
/
/
[1] []
/ /
/ /
[1 2] [1] [2] []
/ / / /
[1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []
class Solution {
public:
typedef vector<int> v;
void recursion(int start,v nums,v tmp, vector<v>& ret)
{
ret.push_back(tmp);
int n = nums.size();
for(int i = start;i < n;i++)
{
tmp.push_back(nums[i]);
recursion(i+1,nums,tmp,ret);
tmp.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ret;
v tmp;
recursion(0,nums,tmp,ret);
return ret;
}
};
解法二：非递归，nums中的数字一个个处理，从空集开始，加入nums[0],然后在上一次产生的集合的基础上继续加入下一个数字nums[1],一直下去直到生成处理完所有数字。
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ret(1);
int i,j,n = nums.size();
for(i = 0;i < n;i++)
{
int m = ret.size();
for(j = 0;j < m;j++)
{
ret.push_back(ret[j]);
ret.back().push_back(nums[i]);
}
}
return ret;
}
};
