一、问题描述
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意： 解集不能包含重复的组合。
题目链接：组合总和 II
二、题目要求
样例
输入: candidates = [2,5,2,1,2], target = 5,输出:[[1,2,2],[5]]
复制代码
考察
三、问题分析
本题是开启回溯算法刷题的第2题，之前没有了解过可以看一下这篇题解，讲解比较详细。
算法题每日一练---第85天：组合
对于这一题最重要的步骤就是判重，因为[1 1 6]和[1 6 1]代表相同的结果。
遍历的话和算法题每日一练---第85天：组合原理是一样的。
第一式：函数初始
我们要初始化一个函数来承载回溯，函数里面的参数如何确定呢？
首先，要传入给定的数组信息，目标值，初始遍历的下标。
vector<int>t;vector<vector<int>> v;void DFS(int begin,int target,vector<int>& candidates)//函数初始
复制代码
第二式：终止条件
什么时候结束继续向下开始搜索的条件呢？
题目要求 target 可以由数组的哪些元素组成，每加入一个元素，target 要减去这个元素的值。
如果 target==0，那么就符合终止条件。
if(target==0)//终止条件{ v.push_back(t); return;}
复制代码
第三式：剪枝优化
这一题剪枝比较简单，上面终止的条件不是等于 0 咩。
那如果 target 已经小于 0，那我们还有必要继续搜索吗，完全没必要。
第四式：递归处理
for(i=begin;i<candidates.size();i++)//递归处理{ if(i>begin && candidates[i]==candidates[i-1])//判重 continue; if(candidates[i]<=target) { t.push_back(candidates[i]); DFS(i+1,target-candidates[i],candidates); t.pop_back(); }}
复制代码
这一题最难搞懂的是判重是如何实现的，首先我们将图中的元素进行排序处理，结果为：
[1,2,2,2,5]
那么相同的元素就会相邻，如上图最左侧的分支，-2 会进行三个操作，但三个操作我们只需要一个，另外的两个分支都是相同的遍历。所以，这里我们也要进行剪枝操作。
那如何剪枝？
在循环遍历里面执行，只要在 begin 遍历之后的元素值和前一个值相同，那么就跳过，不进行操作。
模板：
void DFS(变量)//函数初始{ if(条件1||条件2...)//终止条件 { v.push_back(t); return; } if (条件1||条件2...)//剪枝 return; for(int i=cur;i<=n;i++)//递归处理 { //选择当前数字 DFS(向下遍历); //回退 } }
复制代码
冲冲冲！
四、编码实现
class Solution {public: vector<int>t; vector<vector<int>> v; void DFS(int begin,int target,vector<int>& candidates)//函数初始 { int i; if(target==0)//终止条件 { v.push_back(t); return; } if(target<0)//剪枝优化 return; for(i=begin;i<candidates.size();i++)//递归处理 { if(i>begin && candidates[i]==candidates[i-1])//判重 continue; if(candidates[i]<=target) { t.push_back(candidates[i]); DFS(i+1,target-candidates[i],candidates); t.pop_back(); } } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end());//排序 DFS(0,target,candidates); return v; }};
复制代码
五、测试结果
评论