达州做网站
大橙子网站建设，新征程启航
为企业提供网站建设、域名注册、服务器等服务
005.组合总和II-创新互联
1.题目链接：
文章题目：005.组合总和II-创新互联
本文链接：http://dzwzjz.com/article/jhiji.html
40. 组合总和 II
树层：同层遍历
树枝：递归遍历
2.1.题目要求：给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例：输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]
2.2.思路：这也是构造一颗n叉树，for循环里面套递归，不过这里题目的要求有变化，
输入的数组 candidates 的每一个数字只能用一次，但是数组里又有重复值的元素。
比如 [2,5,2,1,2]的输出[1,2,2]，里面的两个 2 用了 [2,5,2,1,2] 里的随机两个，是满足题目的定义的
而且要求输出的 组合 不能重复
比如：组合（1，2，2）再输出一个（1，2，2）或者（2，2，1）是不行的。
在这个条件怎么让输出的组合不重复？（去重操作）
去重的是同一树层上的“使用过”的数字，同一树枝上的都是一个组合里的元素，不用去重
总体思路就是：
在 “构造一颗n叉树，for循环里面套递归” 的基础上，加上 去重操作
流程如图：
先给数组排个序，用于剪枝和数层去重判断。
2.3.1.确定回溯函数参数用used数组来去重（后面说明）
vector>result; // 存放组合集合
vectorpath; // 符合条件的组合
void backtracking(vector& candidates, int target, int sum, int startIndex,
vector& used) { 这里sum >target ，在剪枝的时候会去掉（剪枝的时候说明）
if (sum >target) { // 这个条件其实可以省略
return;
}
if (sum == target) {
result.push_back(path);
return;
}1.used的目的是跳过同一树层使用过的元素，怎么操作的？（数组已排序）
利用数组 candidates [ i ] 和 [ i-1 ] 的关系，判断前后是否是重复的数字，
然后由usd的值对其 [ i-1 ] 进行判断（i-1是当前树枝的上一层），used到了一个树枝的时候其对应的used[ i ]就会变成 1 ，回溯的时候变成 0 。
2.used判断的依据是：
当进行树枝搜索的时候，其上面一层used的 [ i-1 ] 永远是 1，
而进行树层搜索的时候，其上面一层的used [ i-1 ] 永远是 0。（只有它本层的use [i] = 1 ）
这样的话，
当遇见candidates 的 [ i ] 等于 [ i-1 ] 的时候，用used [ i-1 ] 判断其是 树层 还是 树枝 ，再做相应的去重操作就好了
3.流程如图：
4.used代码中对应的大概操作：
// 用于终止条件，对同一树层使用过的元素进行跳过
if (i >0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) continue;
//用于for循环，添加递归一层为1，回溯一层为0的逻辑
for(){
used[i] = true;
backtracking(candidates, target, sum, i + 1, used);//做隔开
used[i] = false;
}5.完整片段代码：
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：这里是i+1，每个数字在每个组合中只能使用一次
used[i] = false;
sum -= candidates[i];
path.pop_back();
}class Solution {
private:
vector>result;
vectorpath;
void backtracking(vector& candidates, int target, int sum, int startIndex, vector& 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，这里是i+1，每个数字在每个组合中只能使用一次
used[i] = false;
sum -= candidates[i];
path.pop_back();
}
}
public:
vector>combinationSum2(vector& candidates, int target) {
vectorused(candidates.size(), false);
path.clear();
result.clear();
// 首先把给candidates排序，让其相同的元素都挨在一起。
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, 0, used);
return result;
}
}; 给出的数组 candidates 元素可以重复，输出的组合不可以重复，输出的组合里的元素值可以重复，他们之间的具体关系是？
used在代码中去重的逻辑思路是？
4.记录第一天：好复杂的去重，概率也混杂，不容易区分，搞半天只大概理解题意，和一部分的步骤..
第二天：used是怎么操作的？ 完成，
确实抽象，组合总和 | || ||| 确实大部分是一个套路的，一开始觉得应该都差不多，写了后发现，确实都差不多，但又差很多..
写下代码，再修改笔记，把整体思路履顺来。
摸了半天才写代码，发现酝酿那么久还是很有效果的嘛，不过写的时候既然一汽呵成，那么也表示我对这道题目的理解可能也没有问题了，不过对于used这块的操作，后面还是要多想一下
写的时候感觉是拼高达一样拼起来的..
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
文章题目：005.组合总和II-创新互联
本文链接：http://dzwzjz.com/article/jhiji.html