LeetCode 90 子集II
90.子集II
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
回溯递归
此处和 40.组合总和II 较为相似，在集合中存在重复的元素，在结果中需要防止重复选取问题，也就是在回溯时，对于当前元素 nums[cur] 需要跳过后面全部与他值相同的元素。（依旧是存在两种处理方式，一个是使用for循环进行跳过，两外则是对重复元素进行统计，在递归时分别处理选取 0-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
30
31
| class Solution {
public:
vector<pair<int,int>> freq;
vector<int> tmp;
vector<vector<int>> res;
void DFS(int cur){
if(cur==freq.size()){
res.push_back(tmp);
return;
}
DFS(cur+1);
for(int i=1;i<=freq[cur].second;i++){
tmp.push_back(freq[cur].first);
DFS(cur+1);
}
for(int i=1;i<=freq[cur].second;i++)
tmp.pop_back();
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end());
for(auto &a:nums){
if(freq.empty()||freq.back().first!=a){
freq.push_back({a,1});
}else{
freq.back().second++;
}
}
DFS(0);
return res;
}
};
|
注：此处必须使用vector代替map去进行数据个数的统计，因为map是不支持顺序访问的。
另一种跳过方式：在官方题解中给出了一种向前看实现跳过的方式，基本思想就是，对于当前元素首先采取不选取的方式进行递归，并且在递归时传递参数 choosePre=false ，在递归返回后，若本次递归的 choosePre==false 并且当前元素与前一个元素相同，那么就直接返回，实现跳过。（本质上，对于当前元素而言就是，在递归中仅仅采取了不选取的情形进行递归。）
相较于数组统计个数的方式，在空间复杂度上明显降低。此处 choosepre 表示上一个元素是否进行了选取。 cur=0 时，不存在上一个元素，因此肯定是没选，那么在进入递归后，选取了当前元素，在下一次递归中就置 choosePre=true ，在没有选取当前元素则将其置为 false 。
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
| class Solution {
public:
vector<int> t;
vector<vector<int>> ans;
void dfs(bool choosePre, int cur, vector<int> &nums) {
if (cur == nums.size()) {
ans.push_back(t);
return;
}
dfs(false, cur + 1, nums);
if (!choosePre && cur > 0 && nums[cur - 1] == nums[cur]) {
return;
}
t.push_back(nums[cur]);
dfs(true, cur + 1, nums);
t.pop_back();
}
vector<vector<int>> subsetsWithDup(vector<int> &nums) {
sort(nums.begin(), nums.end());
dfs(false, 0, nums);
return ans;
}
};
|
基于迭代法实现
对于包含n个元素的集合，构建他的全部子集，对于每一个元素而言只有选和不选两种状态，因此总计 个状态，使用一个n位的二进制数即可描述。因此只要构造 0/1 序列，按照 0/1 序列在原集合当中取数即可完成穷举。
首先是总体数据的循环控制： 内进行循环， mask 代表选取元素的二进制序列，从0开始，要是实现元素的选取就需要判断 mask 的每一位， mask 总计n位，因此内层循环n次。
逐位判断的实现：判断某个数的第i+1位是0/1，使用与运算实现。
相较于不包含重复元素集合的子集求解：不同之处在于对于 [1,2,2] 中两个 [1,2] 的处理。处理方式为：对于当前选取的元素 nums[cur] 若是在 nums[cur-1]==nums[cur] ，那么说明此时生成的序列是存在重复的，直接结束当前序列子集的生成。使用一个 flag 记录当前子集的生成是否被提前终端来决定是否将其加入到结果集合中。
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
| class Solution {
public:
vector<int> tmp;
vector<vector<int>> res;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end());
int n=nums.size();
for(int mask=0;mask<(1<<n);mask++){
bool flag=true;
tmp.clear();
for(int i=0;i<n;i++){
if(mask&(1<<i)){
if(i!=0&&nums[i]==nums[i-1]&&(mask&(1<<(i-1)))==0){
flag=false;
break;
}else{
tmp.push_back(nums[i]);
}
}
}
if(flag){
res.push_back(tmp);
}
}
return res;
}
};
|