回溯算法去重的两种写法
关于回溯，无论是排列、组合、子集，都会涉及到两个问题，一个是去重，另一个则是剪枝；
去重通常有几种方法。
以这道题来做验证。
90.子集II
力扣题目链接(opens new window)
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
- 输入: [1,2,2]
- 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
used数组
用一个全局变化的used数组来记录是否重，used[0] == true即代表用过了。
这里要进行
-
是需要去统一树枝的重还是同一层高度的重？
-
去重之前应该进行哪些工作？
-
怎么样判断去重？
首先去重之前必定先排列
原因是更加方便的去重，因为排列后相同的元素会相邻，这样就有利于去重的判断
其次通过一张图可以回答第一个问题（图引用自《代码随想录》
可以清晰看到，去重去的应该是同一层的树枝。
剩下则是去重的工作如何进行了。
同时上面那张图已经做了解答
在nums[i] == nums[i-1]的情况下，used[i-1] == false则是同一树层元素相同。
如果是used[i-1] == true，则是同一树枝元素相同。
代码
class Solution {
private:
vector<int> path;
vector<vector<int>> res;
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<bool> used(nums.size(),false);
sort(nums.begin(),nums.end());
backtracking(nums,used,0);
return res;
}
void backtracking(vector<int>& nums,vector<bool>& used, int startindex){
res.push_back(path);
for(int i=startindex;i<nums.size();i++){
if(i>0 && nums[i] == nums[i-1] && used[i-1] == false){
continue;
}
used[i] = true;
path.push_back(nums[i]);
backtracking(nums,used,i+1);
path.pop_back();
used[i] = false;
}
}
};
set去重
set去重则是利用了数据结构本身的特点。即不需要再去做判断，只需判断当前元素是否已经存在即可。
重点是set数组应该怎么样初始化？
- 全局变量
- 在for循环一层前
很明显，如果是全局变量，set数组记录的则是全部树枝的元素记录
这和我们之前得出的结论不同，我们应该要去掉同一层树枝的重。
因此只有在for循环每一层前初始化才能实现。
代码如下
class Solution {
private:
vector<int> path;
vector<vector<int>> res;
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<bool> used(nums.size(),false);
sort(nums.begin(),nums.end());
backtracking(nums,used,0);
return res;
}
void backtracking(vector<int>& nums,vector<bool>& used, int startindex){
res.push_back(path);
unordered_set<int> uset;
for(int i=startindex;i<nums.size();i++){
if(uset.find(nums[i]) != uset.end()){
continue;
}
uset.insert(nums[i]);
path.push_back(nums[i]);
backtracking(nums,used,i+1);
path.pop_back();
}
}
};
h_back(nums[i]);
backtracking(nums,used,i+1);
path.pop_back();
}
}
};
