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],
[]
]
Solution: 1. Recursive solution.
2. Iterative solution. Contributed by
yinlinglin.
1 class Solution {
2 public:
3
4 vector<vector<int> > subsets(vector<int> &S) {
5 vector<vector<int> > res;
6 sort(S.begin(), S.end());
7 vector<int> set;
8 int N = S.size();
9 for(int i = 0; i <= N; i++) {
10 subsets(S, 0, i, set, res);
11 }
12 return res;
13 }
14
15 void subsets(vector<int> &S, int start, int length, vector<int> &set, vector<vector<int> > &res) {
16 if(set.size() == length) {
17 res.push_back(set);
18 return;
19 }
20 int N = S.size(), M = set.size();
21 for(int i = start; i < N - (length-M) + 1; i++) {
22 set.push_back(S[i]);
23 subsets(S, i+1, length, set, res);
24 set.pop_back();
25 }
26 }
27 };
10. 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 class Solution {
2 public:
3 vector<vector<int> > subsetsWithDup(vector<int> &S) {
4 vector<vector<int> > res;
5 vector<int> set;
6 int N = S.size();
7 sort(S.begin(), S.end());
8 res.push_back(vector<int>());
9 for(int i = 1; i <= N; i++) {
10 subsetsWithDupRe(S, 0, i, set, res);
11 }
12 return res;
13 }
14
15 void subsetsWithDupRe(vector<int> &S, int start, int length, vector<int> &set, vector<vector<int> > &res)
16 {
17 int N = S.size(), M = set.size();
18 if(M == length) {
19 res.push_back(set);
20 return;
21 }
22 for(int i = start; i < N - (length-M) + 1; i++) {
23 if(i > start && S[i] == S[i-1]) continue;// duplicate
24 set.push_back(S[i]);
25 subsetsWithDupRe(S, i+1, length, set, res);
26 set.pop_back();
27 }
28
29 }
30 };
原文：http://www.cnblogs.com/zhengjiankang/p/3646370.html