90.子集II
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
- 输入: [1,2,2]
- 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
思路
基本想法
相比于70题，只是多了一个可能包含重复元素，只需要在递归之前检查当前元素是否重复即可，所以形成的搜索树会有一些树枝被剪掉
但是给定的nums可能是无序的，所以需要先进行排序，让重复的元素挨在一起，才可以执行去重操作，避免出现重复子集。
执行流程
也是分为横向遍历和纵向遍历，只不过在每次横向遍历的过程中需要增加条件进行筛选，重复元素不能选取，否则会出现多次从同一个x开始进行搜索的情况
例如[1,2,2,3]，不加筛选条件可能会出现两次从2开始形成子集的情况，筛选条件如下：
1
2
3
4
| //当不是当前层横向遍历的第一个元素时，就可能出现重复子集的情况
if(index==nums.size()){
return;
}
|
代码
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
32
33
34
35
36
| class Solution {
public:
//全局变量存放结果
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
if(nums.size()==0){
return res;
}
//vector自身没有sort函数
//因为它可以随机访问，没必要增加自带sort函数
sort(nums.begin(),nums.end());
backtrack(nums,0);
return res;
}
void backtrack(vector<int>& nums,int index){
res.push_back(path);
if(index==nums.size()){
return;
}
//进行横向搜索
for(int i=index;i<nums.size();++i){
//需要增加筛选条件
//之前从x开始搜索过，之后就不必再从x开始搜索
if(i>index&&nums[i]==nums[i-1]){
continue;
}
//元素没有重复
path.push_back(nums[i]);
//进行递归纵向遍历
backtrack(nums,i+1);
//回溯
path.pop_back();
}
}
};
|
总结
出现重复元素求幂集，可能会出现重复元素的搜索，从而出现重复的子集，所以需要去重，基本思路是排序+筛选，当横向遍历的不是当前层的第一个元素时就需要筛选