Leetcode典型题解答和分析、归纳和汇总——T40（组合总和II）
题目描述：
给定一个数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。注意candidate中的每个数字在组合过程中只能使用一次。
说明：所有数字（包括目标数）都是正整数+解集不能包含重复的组合
解析：
本题与T39具有异曲同工之妙，都可以采用回溯算法来进行求解。该题有两个需要注意的点
【1】数组元素不能出现重复的数字【2】不能出现重复的组合
首先我们把这个数组进行排序（升序），数组中的每个数字在每个组合中只能使用1次，那就按照顺序依次减去数组中的元素，递归求解即可：遇到0就结算回溯，遇到负数也进行回溯。对于遇到的重复的数字，在搜索过程中，找到可能发生重复结果的分支，把它剪掉。
回溯算法的基本模板：
void DFS(int i, int n, other parameter)
{
if（满足条件）
{
记录答案
return;
}
else //求解空间第i个位置的下一个解
for(next ans in position i of solution space)
DFS(i+1,n, other position);
ans.pop_back(); //不满足回溯条件，返回
}
class Solution{
public:
vector<vector> combinationSum2(vector& candidates, int target){
vector<vector> results;//返回的结果
vector path; //选择列表
sort(candidates.begin(),candidates.end());
DFS(candidates,target,0,path,results);
return results; //回溯算法完成后，返回结果
}
void DFS(vector<vector>& candidates, int target, int start, vector<vector>& results)
{
if(target==0)
{
results.push_back(path); //满足条件，则对该路径进行保存
return;
}
for(int i=start;i=candidates[i];i++)
{
if(i>start&&candidates[i]==candidates[i-1]) //表示同一行选择列表相同，比如左边是1，右边也是1
continue; //为了防止重复，进行剪枝处理，跳过回溯
}
results.push_back(candidates[i]); //这一轮结果进行保存
DFS(candidates,target-candidates[i],i+1,path,results);
//这个递归过程详细讲解如下：
//第一个参数还是把原始候选列表candidates输入进去
//第二个参数表示改变了目标值=原始目标值-candidates[i]，减少了
//第三个参数表示不重复使用这个数字i，因此该轮迭代从i+1开始
//第四个数字表示当前的已经保存了的路径path
//第五个参数表示所有的路径保存的集合
results.pop_back(); //不满足条件之后，进行回溯，删除最末尾的数字
}
};
作者：探索者FXJ
