118、【回溯算法】leetcode ——40. 组合总和 II:回溯法+剪枝优化(C++版本)
2023-09-11 14:20:01 时间
题目描述
原题链接:40. 组合总和 II
解题思路
1、visited标记去重
本题的特点是,一个允许结果中出现相同数字,但每个元素仅能被选取一次。结果与结果之间不允许有重复,需要去重。
与 77. 组合(回溯法+剪枝优化) 的相同之处在于选取的元素都是只能被选一次,不同之处在于77里面没有重组元素。
与 39. 组合总和(剪枝优化) 的相同之处在于结果中可能会含有重复元素,但结果与结果之间不能重复。不同之处在于,元素可能被选多次。
- 元素只能被选一次:
考虑了上述个相关题目的思路,依旧设置startIndex = i + 1
控制起始位置,保证每个元素仅被选中一次。 - 结果集中去重:
(1)若数组中元素都不相同,则根据startIndex = i + 1
可知,每次选取的都为不相同元素,则不会出现重复结果集。
(2)若数组中含有相同元素,则可能会出现重复的情况是之前已经某一相同元素与其余相同元素组合符合目标之和,当再选取此时的相同元素元素时,会与哪几个其余元素拼凑再一次导致出现重复结果。例如nums = [1, 1, 2], target = 3
,则会出现两次选择[1, 2]
。
因此,采取的措施是,当第一次遍历到含有相同元素的数时,正常遍历,当第二次遍历到上一次有重复元素的数,跳过该种情况即可。判定条件为i > 0 && candidates[i] == candidates[i - 1]
,但因为第一次遍历时,递归到下一个数时,也是会有1
,但此时第一次遍历时还没结束,不能被跳出。因此需要再设置一个bool
型向量visited
判定上一个重复元素是否为本轮正被遍历元素,如果正被遍历元素,则继续正常向下遍历,直至完成该次遍历。如果不是,则说明是新一轮遍历,为了去重,直接跳过该次遍历。
class Solution {
public:
vector<vector<int>> res;
vector<int> index;
void backtracking(vector<int>& candidates, int target, int startIndex, vector<int> path, vector<bool> visited) {
if(target == 0) {
res.push_back(path);
return ;
}
for(int i = startIndex; i < candidates.size(); i++) {
// 剪枝优化
if(target - candidates[i] < 0) return ;
// i > 0 保证i-1不越界,candidates[i - 1] == candidates[i]判定是否前方有重复元素,visited[i - 1] == false判定为该元素的第一次正被遍历,还是已被遍历过,出现的新一轮遍历
if(i > 0 && candidates[i - 1] == candidates[i] && visited[i - 1] == false) {
// 当该元素已被遍历过,此次为新一轮遍历时,则跳过该种情况
continue;
}
visited[i] = true;
path.push_back(candidates[i]);
backtracking(candidates, target - candidates[i], i + 1, path, visited);
path.pop_back();
visited[i] = false;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> path;
vector<bool> visited(candidates.size(), false);
// 先排序,再剪枝优化
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, path, visited);
return res;
}
};
2、startIndex判定是否去重
startIndex
表示某次遍历的首个元素,根据i
和startIndex
的关系大小,先去重会出现重复元素的结果,然后再让唯一情况加入结果集。
当i == startIndex
时,说明此时刚开始遍历某一数字。当i > startIndex
时,说明已经遍历过前方的元素,正向后续遍历,若此时也出现candidates[i - 1] == candidates[i]
,则说明会出现重复情况,提前跳出该情况。
class Solution {
public:
vector<vector<int>> res;
vector<int> index;
void backtracking(vector<int>& candidates, int target, int startIndex, vector<int> path) {
if(target == 0) {
res.push_back(path);
return ;
}
for(int i = startIndex; i < candidates.size(); i++) {
if(target - candidates[i] < 0) return ;
if(i > startIndex && candidates[i - 1] == candidates[i]) {
continue;
}
path.push_back(candidates[i]);
backtracking(candidates, target - candidates[i], i + 1, path);
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> path;
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, path);
return res;
}
};
原题链接:40.组合总和II
相关文章
- qt实现web服务器加载vue应用进行C++和html混合编程-连载【6】-企业级系统开发实战连载系列 -技术栈(vue、element-ui、qt、c++、sqlite)
- 用C#调用C++DLL(x64),总是提示找不到DLL
- C++STL之string类
- C/C++编译和链接过程详解 概述 (重定向表,导出符号表,未解决符号表)
- C++ 通讯录管理系统
- 【C++】STL常用算法
- 201、【数组】leetcode ——面试题 17.05. 字母与数字(C++版本)
- 199、【哈希表】leetcode ——6315. 统计范围内的元音字符串数(C++版本)
- 184、【栈与队列】leetcode ——739. 每日温度(C++版本)
- 181、【动态规划】leetcode ——72. 编辑距离(C++版本)
- 176、【动态规划】leetcode ——1143. 最长公共子序列(C++版本)
- 174、【动态规划/贪心算法/滑动窗口】leetcode ——674. 最长连续递增序列:一题多解 (C++版本)
- 159、【动态规划】leetcode ——322. 零钱兑换:二维数组+一维滚动数组(C++版本)
- 143、【回溯算法】leetcode ——738. 单调递增的数字:暴力法+贪心法(C++版本)
- 141、【贪心算法】leetcode ——56. 合并区间(区间重叠解法+双指针解法)(C++版本)
- 135、【贪心算法】leetcode ——135. 分发糖果(多维度贪心)(C++版本)
- 133、【贪心算法】leetcode ——1005. K 次取反后最大化的数组和(模拟变化+贪心策略)(C++版本)
- 131、【贪心算法】leetcode ——55. 跳跃游戏(贪心策略)(C++版本)
- 129、【动态规划/贪心算法】leetcode ——53. 最大子数组和(C++版本)
- 119、【回溯算法】leetcode ——131. 分割回文串:分割问题(C++版本)
- 117、【回溯算法】leetcode ——39. 组合总和:回溯法+剪枝优化(C++版本)
- 109、【树与二叉树】leetcode ——701. 二叉搜索树中的插入操作:递归法+双指针迭代法(C++版本)
- 99、【树与二叉树】leetcode ——113. 路径总和 II:回溯法两种版本(C++版本)
- 93、【树与二叉树】leetcode ——222. 完全二叉树的节点个数:普通二叉树求法+完全二叉树性质求法(C++版本)
- 89、【树与二叉树】leetcode ——101. 对称二叉树:后序递归+迭代法+层次遍历(C++版本)
- 84、【栈与队列】leetcode ——1047. 删除字符串中的所有相邻重复项:栈+双指针解法(C++版本)
- 82、【栈与队列】leetcode ——225. 用队列实现栈(C++版本)
- 71、【哈希表】leetcode——350. 两个数组的交集 II(C++版本)
- 70、【哈希表】leetcode——1. 两数之和(C++版本)
- C++实操 - Event概念介绍和定义一个Event类
- C++基础 工资和奖金