网站icp备案信息如何查询,公司品牌策划设计,四川省建设厅网站打不开,制作团购网站力扣题目链接(opens new window)
给定一个数组 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明#xff1a; 所有数字#xff08;包括目标数#xff09;都是…
力扣题目链接(opens new window)
给定一个数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明 所有数字包括目标数都是正整数。解集不能包含重复的组合。
示例 1:输入: candidates [10,1,2,7,6,1,5], target 8,所求解集为:
[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]
]示例 2:输入: candidates [2,5,2,1,2], target 5,所求解集为:
[[1,2,2],[5]
]#思路
这道题目和39.组合总和 (opens new window)如下区别
本题candidates 中的每个数字在每个组合中只能使用一次。本题数组candidates的元素是有重复的而39.组合总和 (opens new window)是无重复元素的数组candidates
最后本题和39.组合总和 (opens new window)要求一样解集不能包含重复的组合。
本题的难点在于区别2中集合数组candidates有重复元素但还不能有重复的组合。
一些同学可能想了我把所有组合求出来再用set或者map去重这么做很容易超时
所以要在搜索的过程中就去掉重复组合。
很多同学在去重的问题上想不明白其实很多题解也没有讲清楚反正代码是能过的感觉是那么回事稀里糊涂的先把题目过了。
这个去重为什么很难理解呢所谓去重其实就是使用过的元素不能重复选取。 这么一说好像很简单
都知道组合问题可以抽象为树形结构那么“使用过”在这个树形结构上是有两个维度的一个维度是同一树枝上使用过一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。
那么问题来了我们是要同一树层上使用过还是同一树枝上使用过呢
回看一下题目元素在同一个组合内是可以重复的怎么重复都没事但两个组合不能相同。
所以我们要去重的是同一树层上的“使用过”同一树枝上的都是一个组合里的元素不用去重。
为了理解去重我们来举一个例子candidates [1, 1, 2], target 3方便起见candidates已经排序了
强调一下树层去重的话需要对数组排序
选择过程树形结构如图所示 可以看到图中每个节点相对于 39.组合总和 (opens new window)我多加了used数组这个used数组下面会重点介绍。
#回溯三部曲
递归函数参数
与39.组合总和 (opens new window)套路相同此题还需要加一个bool型数组used用来记录同一树枝上的元素是否使用过。
这个集合去重的重任就是used来完成的。
代码如下
vectorvectorint result; // 存放组合集合
vectorint path; // 符合条件的组合
void backtracking(vectorint candidates, int target, int sum, int startIndex, vectorbool used) {递归终止条件
与39.组合总和 (opens new window)相同终止条件为 sum target 和 sum target。
代码如下
if (sum target) { // 这个条件其实可以省略return;
}
if (sum target) {result.push_back(path);return;
}sum target 这个条件其实可以省略因为在递归单层遍历的时候会有剪枝的操作下面会介绍到。
单层搜索的逻辑
这里与39.组合总和 (opens new window)最大的不同就是要去重了。
前面我们提到要去重的是“同一树层上的使用过”如何判断同一树层上元素相同的元素是否使用过了呢。
如果candidates[i] candidates[i - 1] 并且 used[i - 1] false就说明前一个树枝使用了candidates[i - 1]也就是说同一树层使用过candidates[i - 1]。
此时for循环里就应该做continue的操作。
这块比较抽象如图 我在图中将used的变化用橘黄色标注上可以看出在candidates[i] candidates[i - 1]相同的情况下
used[i - 1] true说明同一树枝candidates[i - 1]使用过used[i - 1] false说明同一树层candidates[i - 1]使用过
可能有的录友想为什么 used[i - 1] false 就是同一树层呢因为同一树层used[i - 1] false 才能表示当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。
而 used[i - 1] true说明是进入下一层递归去下一个数所以是树枝上如图所示 这块去重的逻辑很抽象网上搜的题解基本没有能讲清楚的如果大家之前思考过这个问题或者刷过这道题目看到这里一定会感觉通透了很多
那么单层搜索的逻辑代码如下
for (int i startIndex; i candidates.size() sum candidates[i] target; i) {// used[i - 1] true说明同一树枝candidates[i - 1]使用过// used[i - 1] false说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过if (i 0 candidates[i] candidates[i - 1] used[i - 1] false) {continue;}sum candidates[i];path.push_back(candidates[i]);used[i] true;backtracking(candidates, target, sum, i 1, used); // 和39.组合总和的区别1这里是i1每个数字在每个组合中只能使用一次used[i] false;sum - candidates[i];path.pop_back();
}注意sum candidates[i] target为剪枝操作在39.组合总和 (opens new window)有讲解过
回溯三部曲分析完了整体C代码如下
class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIndex, vectorbool used) {if (sum target) {result.push_back(path);return;}for (int i startIndex; i candidates.size() sum candidates[i] target; i) {// used[i - 1] true说明同一树枝candidates[i - 1]使用过// used[i - 1] false说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过if (i 0 candidates[i] candidates[i - 1] used[i - 1] false) {continue;}sum candidates[i];path.push_back(candidates[i]);used[i] true;backtracking(candidates, target, sum, i 1, used); // 和39.组合总和的区别1这里是i1每个数字在每个组合中只能使用一次used[i] false;sum - candidates[i];path.pop_back();}}public:vectorvectorint combinationSum2(vectorint candidates, int target) {vectorbool used(candidates.size(), false);path.clear();result.clear();// 首先把给candidates排序让其相同的元素都挨在一起。sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
}; 时间复杂度: O(n * 2^n)空间复杂度: O(n)
#补充
这里直接用startIndex来去重也是可以的 就不用used数组了。
class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIndex) {if (sum target) {result.push_back(path);return;}for (int i startIndex; i candidates.size() sum candidates[i] target; i) {// 要对同一树层使用过的元素进行跳过if (i startIndex candidates[i] candidates[i - 1]) {continue;}sum candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i 1); // 和39.组合总和的区别1这里是i1每个数字在每个组合中只能使用一次sum - candidates[i];path.pop_back();}}public:vectorvectorint combinationSum2(vectorint candidates, int target) {path.clear();result.clear();// 首先把给candidates排序让其相同的元素都挨在一起。sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0);return result;}
}; #总结
本题同样是求组合总和但就是因为其数组candidates有重复元素而要求不能有重复的组合所以相对于39.组合总和 (opens new window)难度提升了不少。
关键是去重的逻辑代码很简单网上一搜一大把但几乎没有能把这块代码含义讲明白的基本都是给出代码然后说这就是去重了究竟怎么个去重法也是模棱两可。
所以Carl有必要把去重的这块彻彻底底的给大家讲清楚就连“树层去重”和“树枝去重”都是我自创的词汇希望对大家理解有帮助
