leetcode-40-组合总和 II
leetcode-40-组合总和 II
题目描述：
给定一个数组 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]
]要完成的函数：
vector<vector<int>> combinationSum2(vector<int>& candidates, int target)
说明：
1、这道题给定一个vector，里面装着几个正整数，正整数可以是重复的，还给了一个正整数的target。
要求找出所有组合，使得每个组合中的正整数的和等于target。
不能重复使用某一个数。
每个组合以一维vector的形式存储，最终所有组合存储在二维vector中，返回二维vector。
2、举个例子，[10,1,2,7,6,1,5]，target是8，我们人类是怎么解决这道题的？
第一个数10，不满足。
第二个数1，可以，但我们还需要7，第三个数2，可以，但我们还需要5，第四个数7不行，第五个数6不行，第六个数1可以，但我们还需要4，第七个数5不行。
然后我们回退到第六个数，我们不要1了，我们还需要5，试探第七个数5，刚好可以。1,2,5
接着再回退一步，我们不要第三个数2了，这时候我们还要7，试探第四个数7，刚好可以。1,7
接着再回退一步，我们不要第四个数7了，这时候我们还需要7，试探第五个数6，可以，我们还需要1，试探第六个数1，刚好可以。1,6,1
接着再回退一步，我们不要第六个数1，我们还需要1，试探第七个数5，不可以，结束。
接着再回退一步……
你会发现这就是一个不断试探的过程，这种题我们适合用递归来做。
要求每个数只能使用一次，这个也简单，我们递归的时候，起始index设置在下一个就好了。
但我们还没有解决重复组合的问题，比如2,5,2,1,2，target是5。
如果我们用递归来做，我们会得到2,2,1，2,1,2，5，2,1,2这样的组合。
对待重复这件事，排序有奇效。
我们简单排个序，变成1,2,2,2,5，同样递归来做，得到1,2,2，我们看到下一个数跟当前数是一样的，那么再往前走一步，试探5，就不要试探第三个2了。
这样可以快速地解决重复组合的问题。
代码如下：（附详解）
vector<vector<int>>res;//全局变量，最终要返回的二维vector
vector<int>res1;//全局变量，存储每次可能的组合
void digui(vector<int>& candidates,int index,int target,vector<int>& res1)
{
if(target==0)//满足退出条件
{
res.push_back(res1);//每个组合插入到res中
return;//返回到上一层递归
}
while(index<candidates.size())//不断地试探
{
if(candidates[index]<=target)
{
res1.push_back(candidates[index]);//进入递归前，设置好res1
digui(candidates,index+1,target-candidates[index],res1);
res1.pop_back();//退出递归后，恢复res1
}
else//如果发现candidates[index]大于target了，那么不要再试了，直接返回到上一层的递归
return;
while(candidates[index]==candidates[index+1])//想要更新index，如果下一个值跟当前值一样，不断地往前走
index++;
index++;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target)
{
sort(candidates.begin(),candidates.end());//排个序，升序
digui(candidates,0,target,res1);//直接进入递归
return res;//最终返回res
}上述代码实测8ms，beats 98.51% of cpp submissions。
对于这个过程还不太清晰的同学，可以自己手工推导一下所有过程，逻辑会清晰很多。
也可以参考博主上一篇博文leetcode-39-组合总和（有趣的递归），可以说是同个类型的题目。