LeetCode 78. 40. 组合总和 II（C++）
题目描述：
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例一：
输入: candidates =[10,1,2,7,6,1,5], target =8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
示例二：
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]思路：
用了递归回溯的思想，类似于原 LeetCode 78. 子集（C++的三种实现）和原 LeetCode 90. 子集 II (C++)利用只要先排序，并在找出组合时加上剪枝操作再借助set去重就可以了。
找出组合的方法，原链接中有三种方法，我的代码中会使用第三种（当然前两种也可以）。
回溯法：我们可以看到其实这个问题，亦可以理解为每个元素的放入与不放入问题。
选择放入：递归的进行后续元素的选择，完成放入该元素后续所用元素的试探，之后又将其取出，
进行选择不放入：该元素，递归后续元素的选择。完成所有元素的试探。就可以找出所有的排列。
剪枝操作：具体是用了当一个组合的和大于目标数是，后面就不用再加入了。
下面是我的代码：
虽然效率可以，但这个代码的可读性是有点低啊！之前写的自己看着都有点费劲，放上来的原因其实就是记录下学习。大家可以直接看后面代码。
class Solution {
public:
vector<vector<int>> res;//存储最终结果
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());//对数组进行排序，方便去重。
vector<int> vec;
dfs(candidates, vec, target, 0);
return res;
}
void dfs(vector<int>& candidates, vector<int>& vec, int target, int index){
if(target == 0){ //递归出口，当总和达到target时结束递归。
res.push_back(vec); //存储结果
return;
}
for(int i = index;i < candidates.size();i++){ //从index开始继续遍历
if(candidates[i] > target){ //当加上当前元素的数值大与还需要加的
return; //不在进行尝试后面的数字，因为已经排过序了，后面的元素比前面的大，所以不用再尝试。
}
vec.push_back(candidates[i]); //选择加入下标为i的元素
dfs(candidates, vec, target - candidates[i], i+1);继续递归
vec.pop_back(); //选择不加入这个元素
while(i+1 < candidates.size() && candidates[i+1] == candidates[i])//去掉重复元素。
i++;
}
}
};下面的代码用的同一思路：实在不想去理解之前咋写的????，写的太丑了，重新写了一下。这里为了看到剪枝对代码的影响，我写了两段，一段是正常的退出递归，一段加入剪枝。
第一段
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int& target) {
sort(candidates.begin(),candidates.end());//先对数组进行排序
set<vector<int>> output;//用来进行去重的set
int numssize=candidates.size();
int i=0;
vector<int > newtemp;
vector<vector<int>> result;//存储子集所有结果
subsetss(numssize,i,candidates,output,newtemp,result,target);
return result;
}
void subsetss(int numssize,int i,vector<int > &nums,set<vector<int>>& output,vector<int >& newtemp,vector<vector<int>>& result,int& target){
if(target<=0||i>=numssize){ //当目标数达到,或者超过目标时
if(target==0&&output.find(newtemp)==output.end()){//利用set 判断之前用没有加入过，也就是去重
output.insert(newtemp); //记录集合
result.push_back(newtemp);//加入set 进行记录，set中记录的是已经出现的
}
return;
}
newtemp.push_back(nums[i]); //选择加入下标为i的元素。
target=target-nums[i];
subsetss(numssize,i+1,nums,output,newtemp,result,target);//递归进行后续元素
newtemp.pop_back(); //选择不加入下标为i的元素
target=target+nums[i];
subsetss(numssize,i+1,nums,output,newtemp,result,target);//递归进行后续元素的操作
}
};第二段
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int& target) {
sort(candidates.begin(),candidates.end());//先对数组进行排序
set<vector<int>> output;//用来进行去重的set
int numssize=candidates.size();
int i=0;
vector<int > newtemp;
vector<vector<int>> result;//存储子集所有结果
subsetss(numssize,i,candidates,output,newtemp,result,target);
return result;
}
void subsetss(int numssize,int i,vector<int > &nums,set<vector<int>>& output,vector<int >& newtemp,vector<vector<int>>& result,int& target){
if(target<=0||i>=numssize){ //当目标数达到,或者超过目标时
if(target==0&&output.find(newtemp)==output.end()){//利用set 判断之前用没有加入过，也就是去重
output.insert(newtemp); //记录集合
result.push_back(newtemp);//加入set 进行记录，set中记录的是已经出现的
}
return;
}
if(target-nums[i]<0){ //剪枝操作，如果加上这个元素后就超过了预期那么久不用再递归下去了
return;
}
newtemp.push_back(nums[i]); //选择加入下标为i的元素。
target=target-nums[i];
subsetss(numssize,i+1,nums,output,newtemp,result,target);//递归进行后续元素
newtemp.pop_back(); //选择不加入下标为i的元素
target=target+nums[i];
subsetss(numssize,i+1,nums,output,newtemp,result,target);//递归进行后续元素的操作
}
};可以看到效率提高还是很大的。至于99.7-93.86的差距，我觉得是网速的原因????。欢迎大家留言指教，共同讨论。