122、【回溯算法】leetcode ——90. 子集 II:子集去重(C++版本)
2023-09-11 14:20:01 时间
题目描述
原题链接:90. 子集 II
解题思路
本题相对于 78. 子集(子集问题) 的区别在于,数组中可能会含有相同元素,可允许单个结果内有重复,但若还是获取所有树结点的话,会出现结果与结果之间有重复。因此,需要对会出现重复的结果进行去重。
去重方式与 40.组合总和II(bool型变量方法+startIndex去重方法) 相同,可采用判定stratIndex
是否大于i
与判定nums[i]
与nums[i - 1]
是否相同。若大于且相同,则说明有重复元素,因在没有遍历到这个元素之前,已经将这一数字与其余数字的组合结果存储过,因此对于出现相同数字时,跳
过该种情况即可。
1、startIndex去重
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums, int startIndex) {
res.push_back(path);
if(startIndex == nums.size()) return ;
for(int i = startIndex; i < nums.size(); i++) {
// 保存第一次出现某一数字的情况,跳过出现重复数字的情况
if(i > startIndex && nums[i] == nums[i - 1]) continue;
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 去重需要排序,保证相同元素相邻排列
backtracking(nums, {});
return res;
}
};
2、visited去重
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums, int startIndex, vector<bool> visited) {
res.push_back(path);
if(startIndex == nums.size()) return ;
for(int i = startIndex; i < nums.size(); i++) {
// i > 0:保证不越界,nums[i] == nums[i - 1]:判定是否有重复数字,visited[i - 1] == false:说明第一个出现的数字已经被遍历过,此时为重复元素开始遍历,需去重
if(i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == false) continue;
visited[i] = true;
path.push_back(nums[i]);
backtracking(nums, i + 1, visited);
path.pop_back();
visited[i] = false;
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<bool> visited(nums.size(), false);
sort(nums.begin(), nums.end()); // 去重需要排序,保证相同元素相邻排列
backtracking(nums, {}, visited);
return res;
}
};
参考文章:90.子集II
相关文章
- C++ 获取进程所在目录(全路径)
- C++之remove和remove_if
- c++/c 数据结构 new
- 《易学C++(第2版)》——1.5 C语言、C++语言和Visual C++
- 《C++游戏编程入门(第4版)》——1.7 使用常量
- [第四届蓝桥杯省赛C++B组]连号区间数
- C++模板类代码只能写在头文件?
- C++ string 字符串查找匹配
- 203、【栈与队列】leetcode ——剑指 Offer II 040. 矩阵中最大的矩形 / 85. 最大矩形:暴力+单调栈(C++/Pyhont版本)
- 199、【哈希表】leetcode ——6315. 统计范围内的元音字符串数(C++版本)
- 193、【栈与队列】leetcode ——面试题 16.26. 计算器(C++版本)
- 164、【动态规划】leetcode ——213. 打家劫舍 II:环形列表线性化(C++版本)
- 160、【动态规划】leetcode ——279. 完全平方数:二维数组+一维滚动数组(C++版本)
- 154、【动态规划】leetcode ——494. 目标和:回溯法+动态规划(C++版本)
- 150、【动态规划】leetcode ——96. 不同的二叉搜索树(C++版本)
- 147、【动态规划】leetcode ——62. 不同路径:递归法+迭代法(C++版本)
- 146、【动态规划】leetcode ——746. 使用最小花费爬楼梯:递归法+迭代法(C++版本)
- 141、【贪心算法】leetcode ——56. 合并区间(区间重叠解法+双指针解法)(C++版本)
- 138、【贪心算法】leetcode ——452. 用最少数量的箭引爆气球(贪心区间重叠问题)(C++版本)
- 134、【贪心算法】leetcode ——134. 加油站(贪心策略)(C++版本)
- 127、【贪心算法】leetcode ——455. 分发饼干:DFS+双指针法(C++版本)
- 123、【回溯算法】leetcode ——491. 递增子序列:unordered_set去重和int数组去重(C++版本)
- 121、【回溯算法】leetcode ——78. 子集(C++版本)
- 114、【回溯算法】leetcode ——77. 组合:回溯法+剪枝优化(C++版本)
- 81、【栈与队列】leetcode ——232. 用栈实现队列(C++版本)
- 71、【哈希表】leetcode——350. 两个数组的交集 II(C++版本)
- 62、【数组】leetcode——54. 螺旋矩阵:N*M型(C++版本)
- 61、【数组】leetcode——[高频考题]59. 螺旋矩阵 II:N*N型(C++、Python版本)
- 许多其他C++的class样本