# 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处理完成之后，我们可以同样方式处理2，以及3。

```c++
class Solution {
public:
vector > res;
vector > subsets(vector &S) {
if(S.empty()) {
return res;
}

sort(S.begin(), S.end());

//别忘了空集合
res.push_back(vector());

vector v;

generate(0, v, S);

return res;
}

void generate(int start, vector& v, vector &S) {
if(start == S.size()) {
return;
}

for(int i = start; i < S.size(); i++) {
v.push_back(S[i]);

res.push_back(v);

generate(i + 1, v, S);

v.pop_back();
}
}
};
```

# 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],
[]
]
```
>

```c++
class Solution {
public:
vector > res;

vector > subsetsWithDup(vector &S) {
if(S.empty()) {
return res;
}

sort(S.begin(), S.end());

res.push_back(vector());

vector v;

generate(0, v, S);

return res;
}

void generate(int start, vector& v, vector &S) {
if(start == S.size()) {
return;
}

for(int i = start; i < S.size(); i++) {
v.push_back(S[i]);

res.push_back(v);

generate(i + 1, v, S);

v.pop_back();

//这里跳过相同的
while(i < S.size() - 1 && S[i] == S[i + 1]) {
i++;
}
}
}
};
```