朋友做网站网站挣了好多钱,青岛找网站建设公司哪家好,网站建设用户需求调查,室内设计师证需要学哪些课程给定一个候选人编号的集合 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用 一次
注意#xff1a;解集不能包含重复的组合 示例 1:
输入: candidates [10,1,2,7,6,1,5], t…给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用 一次
注意解集不能包含重复的组合 示例 1:
输入: candidates [10,1,2,7,6,1,5], target 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates [2,5,2,1,2], target 5,
输出:
[
[1,2,2],
[5]
] 一解法一used数组
思路和分析本题和这道题的 leetCode 39.组合总和 回溯算法 剪枝 的区别是
不同点
本题candidates 中的每个数字在每个组合中只能使用 一次 本题数组candidates 的元素是有重复的而 leetCode 39. 是无重复元素的数组candidates
相同点
解集不能包含重复的组合
总结此题要求元素在同一个组合内是可以重复的多少次都可以但两个组合不能相同。换句话说“集合数组candidates有重复元素但还不能有重复的组合 ”
举个栗子candidates [1, 1, 2], target 3 注意前提candidates 已经排序了 思考(O_O)?为啥used[i-1] false能表示同一树层candidates[i-1] “使用过” 这种情况呢
是因为在同一树层used[i-1] false 能表示当前取的candidates[i]是从candidates[i-1]回溯而来的used[i]true,表示进入下一层递归取下一个数所以在树枝上 问题思考(O_O)?
1).什么是“去重”
“去重”就是使用过的元素不能重复选取了
2).何为“树枝去重”、“树层去重”代码随想录Carl老师自创的名词
可把组合问题抽象为树形结构used“使用过”在这个树形结构上是有两个维度的一个维度表示是同一树枝上使用过一个维度表示是同一树层上使用过
来看题目要求“集合数组candidates有重复元素但还不能有重复的组合 ”。
故去重的是同一树层上的“使用过”是不同组合里的元素而对于同一树枝上的都是一个组合里的元素不用去重。
强调注意在树层去重时需要对数组排序
回溯三部曲:
1).确定回溯函数参数
path来收集符合条件的结果result 保存 path,作为结果集startIndex 来控制for循环的起始位置used 是bool型数组用来记录同一树枝上的元素是否使用过
vectorvectorint result;
vectorintpath;
void backtracking(vectorint candidates,int sum,int target,vectorboolused,int startIndex)
2).递归的终止条件
sum target 和 sum targe
if (sum target) { // 这个条件其实可以省略return;
}
if (sum target) {result.push_back(path);return;
}
可以写成这样
在递归单层遍历的时候会有剪枝的操作
for(int istartIndex;icandidates.size() sum candidates[i] target;i) {...
}
在这篇文章中有提到 for循环的剪枝操作sum candidates[i] target为「剪枝操作」。感兴趣的小伙伴们可以看一下leetCode 39.组合总和 回溯算法 剪枝https://blog.csdn.net/weixin_41987016/article/details/134672946?spm1001.2014.3001.5501
3).单层搜索的逻辑
去重逻辑if( i0 candidates[i] candidates[i - 1] used[i - 1] false)表示前一个树枝使用了candidates[i - 1]也就是说同一树层使用过candidates[i - 1]。那么此时 for循环 里通过 continue 操作跳过此种情况的递归
for(int istartIndex;icandidates.size() sum candidates[i] target;i) {if(i0 candidates[i]candidates[i-1] used[i-1]false) continue;......
}
C代码
class Solution {
public:vectorvectorint result;vectorintpath;void backtracking(vectorint candidates,int sum,int target,vectorboolused,int startIndex) {if(sum target) {result.push_back(path);return;}for(int istartIndex;icandidates.size() sum candidates[i] target;i) {/*used[i - 1] true说明同一树枝candidates[i - 1]使用过used[i - 1] false说明同一树层candidates[i - 1]使用过要对同一树层使用过的元素进行跳过*/if(i0 candidates[i]candidates[i-1] used[i-1]false) continue;path.push_back(candidates[i]);sumcandidates[i];used[i]true;backtracking(candidates,sum,target,used,i1);// 和39.组合总和的区别1这里是i1每个数字在每个组合中只能使用一次used[i]false;sum-candidates[i];path.pop_back();}}vectorvectorint combinationSum2(vectorint candidates, int target) {vectorbool used(candidates.size(), false);// 首先把给candidates排序让其相同的元素都挨在一起。sort(candidates.begin(),candidates.end()); backtracking(candidates,0,target,used,0);return result;}
};
二解法二不用 used 数组而用 startIndex 来去重
class Solution {
public:vectorvectorint result;vectorintpath;void backtracking(vectorint candidates,int sum,int target,int startIndex) {if(sum target) {result.push_back(path);return;}for(int istartIndex;icandidates.size() sum candidates[i] target;i) {if(istartIndex candidates[i]candidates[i-1]) continue;path.push_back(candidates[i]);sumcandidates[i];backtracking(candidates,sum,target,i1);// 和39.组合总和的区别1这里是i1每个数字在每个组合中只能使用一次sum-candidates[i];path.pop_back();}}vectorvectorint combinationSum2(vectorint candidates, int target) {vectorbool used(candidates.size(), false);// 首先把给candidates排序让其相同的元素都挨在一起。sort(candidates.begin(),candidates.end()); backtracking(candidates,0,target,0);return result;}
};
参考文章和推荐视频
代码随想录 (programmercarl.com)https://www.programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html#%E6%80%9D%E8%B7%AF回溯算法中的去重树层去重树枝去重你弄清楚了没| LeetCode:40.组合总和II_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV12V4y1V73A/?p66spm_id_frompageDrivervd_sourcea934d7fc6f47698a29dac90a922ba5a3
