78. Subsets
描述
Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
分析
这道题要求返回一个给定数组的全部子集，那么我们想到的最简单的方法就是进行枚举，但随着数组中元素数量增加，要枚举的次数也会越来越多，显然这是不现实的。所以我们要从别的角度进行考虑。
假如我们第一次向结果中加入一个空集，结果的状态应该如下:
[
[ ]
]
之后我们加入1这个元素
[
[ ]
[1]
]
然后加入2
[
[ ]
[1]
[1 2]
[2]
]
然后加入3
[
[ ]
[1 2 3]
[2 3]
[3]
]
………………
如此往复最后一定可以得到我们需要的结果，据此我们可以看出，全部子集就是每次先克隆上一个状态，接着向这个克隆的结果中添加新的一个元素，直到所有元素都被添加进去为止。这是一种利用迭代解决此问题的方法，代码如下:
/*Solution1 ,Iteration*/
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int>> res(1);
for(int i=0;i<S.size();++i){
int size=res.size();
for(int j=0;j<size;j++){
res.push_back(res[j]);
res.back().push_back(S[i]);
}
}
return res;
}
};
这个问题还可以利用Backtracking算法来解，准确地说，Backtracking算法是解决这类解为一个空间的问题的通用方法。
我们以[1 2 3 4]为例，分析如何用递归的方式处理这个问题。
subsets([1 2 3 4])=[]
//push(1)
[1,subsets[2 3 4]]
//pop,push(2)
[2,subsets[3,4]]
//pop,push(3)
[3,subsets[4]]
//pop,push(4)
[4,subsets[]]
//pop
避免重复计入，我们每次需要做一次pop操作
那么我们需要从第一个数字开始，通过递归的方式尝试所有的可能，如果结果合法，我们将其放入结果中，如果不合法，我们就需要进行回溯，代码如下：
/*Solution2 Recursion*/
class Solution {
private:
void backtracking(vector<int> & nums,vector<int> & sub,vector<vector<int>> & subs,int start){
subs.push_back(sub);
for(int i=start;i<nums.size();++i){
sub.push_back(nums[i]);
backtracking(nums,sub,subs,i+1);
sub.pop_back();
}
}
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int>> subs;
vector<int> sub;
backtracking(S,sub,subs,0);
return subs;
}
};