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,2,3]，构造的二叉树如下（左子树表示选择该层处理的元素，右子树不选择），最后得到的叶子节点就是子集：
算法1：根据上面的启发，我们可以用dfs来得到树的所有叶子节点，代码如下：
复制代码
1 class Solution {
2 private:
3 vector >res;
4 public:
5 vector > subsets(vector &S) {
6 // IMPORTANT: Please reset any member data you declared, as
7 // the same Solution instance will be reused for each test case.
8 //先排序，然后dfs每个元素选或者不选，最后叶子节点就是所有解
9 res.clear();
10 sort(S.begin(), S.end());
11 vectortmpres;
12 dfs(S, 0, tmpres);
13 return res;
14 }
15 void dfs(vector &S, int iend, vector &tmpres)
16 {
17 if(iend == S.size())
18 {res.push_back(tmpres); return;}
19 //选择S[iend]
20 tmpres.push_back(S[iend]);
21 dfs(S, iend+1, tmpres);
22 tmpres.pop_back();
23 //不选择S[iend]
24 dfs(S, iend+1, tmpres);
25 }
26 };
复制代码
算法2：从上面的二叉树可以观察到，当前层的集合 = 上一层的集合 + 上一层的集合加入当前层处理的元素得到的所有集合（其中树根是空集），因此可以从第二层开始（第一层是空集合）迭代地求最后一层的所有集合（即叶子节点），代码如下：
复制代码
1 class Solution {
2 public:
3 vector > subsets(vector &S) {
4 // IMPORTANT: Please reset any member data you declared, as
5 // the same Solution instance will be reused for each test case.
6 int len = S.size();
7 sort(S.begin(), S.end());
8 vector > res(1);//开始加入一个空集
9 for(int i = 0; i < len; ++i)
10 {
11 int resSize = res.size();
12 for(int j = 0; j < resSize; j++)
13 {
14 res.push_back(res[j]);
15 res.back().push_back(S[i]);
16 }
17 }
18 return res;
19 }
20 };
复制代码
LeetCode:Subsets II
Given a collection of integers that might contain duplicates, 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,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
分析：在上一题的基础上，可以允许集合中包含重复元素，我们也把相应的二叉树画出类，以集合{1,2,2}举例
算法1：dfs解法。注意到处理第三个元素2时，因为前面已经处理了一次2，所有第三层中，我们只在已经添加过2的集合{1,2}、{2}上再添加2，而没有在集合{1}, {}上添加2（画叉叉的那么分支），假设下面还有一个2，那么我们只在第四层的包含两个2的集合{1,2,2}、{2,2}上再添加2，其它都不添加。因此dfs时，如果当前处理的数字前面出现了k次，那么我们要处理的集合中必须包含k个该元素。代码如下：
复制代码
1 class Solution {
2 private:
3 vector >res;
4 public:
5 vector > subsetsWithDup(vector &S) {
6 // IMPORTANT: Please reset any member data you declared, as
7 // the same Solution instance will be reused for each test case.
8 //先排序，然后dfs每个元素选或者不选，最后叶子节点就是所有解
9 res.clear();
10 sort(S.begin(), S.end());
11 vectortmpres;
12 dfs(S, 0, tmpres);
13 return res;
14 }
15 void dfs(vector &S, int iend, vector &tmpres)
16 {
17 if(iend == S.size())