题目链接: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个整数集合(集合中可以包含重复元素),返回其所有子集。要求子集中的元素以非递减的顺序排列,且不包含重复子集。
这是Subsets的扩展,在其基础上使数组中允许重复元素。思路就是在处理Subsets的基础上加个跳过重复元素即可。
其中b为子集的起始位置,n为子集的元素数量。
时间复杂度:O(n*2^n)(结果数量)
空间复杂度:O(n*2^n)(结果数量)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution
{
vector<vector<int> > vvi;
public:
vector<vector<int> > subsetsWithDup(vector<int> &S)
{
sort(S.begin(), S.end());
vector<int> vi;
vvi.push_back(vi);
for(int i = 1; i <= S.size(); ++i)
subsetsWithDup(S, vi, 0, i);
return vvi;
}
private:
// b为子集的起始位置,n为子集的元素数量
void subsetsWithDup(vector<int> &S, vector<int> vi, int b, int n)
{
if(n == 0)
vvi.push_back(vi);
else
for(int i = b; i < S.size() + 1 - n; )
{
vi.push_back(S[i]);
subsetsWithDup(S, vi, i + 1, n - 1);
vi.pop_back();
while(S[++i] == S[i - 1]); // 跳过重复元素
}
}
};