这道题是LeetCode里的第39道题。
题目描述：
给定一个无重复元素的数组
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的数字可以无限制重复被选取。说明：
- 所有数字（包括
target）都是正整数。- 解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
首先一看到题目我能想到的就是递归，但感觉递归太简单实现了，而且递归函数参数多(想起八皇后问题)，想试试别的方法，一看评论区，绝大多数都是回溯剪枝法，递归法，DFS。其实一看代码其实这三种方法几乎一样。
示例二图：
当总和大于等于8时，就可以剪枝了，也就是说后面已经没有了答案。
解题代码：
class Solution {
public:
vector<vector<int>> res;
vector<int> ans;
void getres(vector<int>& candidates,int target,int k,vector<int> ans){
int size=candidates.size();
for(int i=k;i<size;i++){
if(target-candidates[i]>0){
ans.push_back(candidates[i]);
getres(candidates,target-candidates[i],i,ans);
ans.pop_back();
}
else if(target-candidates[i]<0){return;}
else{
ans.push_back(candidates[i]);
res.push_back(ans);
ans.pop_back();
return;
}
}
return;
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
getres(candidates,target,0,ans);
return res;
}
};然后想优化代码，优化就是为了剪枝，缩短运行时间。以下是优化结果，但是运行结果是错的。原因在于我之前写的代码已经具备的剪枝的效果，我后面这样写画蛇添足了。
class Solution {
public:
vector<vector<int>> res;
vector<int> ans;
bool getres(vector<int>& candidates,int target,int k,vector<int> ans){
int size=candidates.size();
for(int i=k;i<size;i++){
if(target-candidates[i]>0){
ans.push_back(candidates[i]);
if(getres(candidates,target-candidates[i],i,ans)){
ans.pop_back();
return false;
}
ans.pop_back();
}
else if(target-candidates[i]<0){return true;}
else{
ans.push_back(candidates[i]);
res.push_back(ans);
ans.pop_back();
return false;
}
}
return false;
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
getres(candidates,target,0,ans);
return res;
}
};提交结果：
个人总结：
本题的数据是可以重复的，可重复加深了答案的深度。还有我一开始没有对数据进行排序，导致一次错误，如果不排序的话，想要得出答案会很麻烦，剪枝步骤也会变得毫无意义，尤其是在大数据下，对数据进行先排序后处理，时间上的优势可以明显的表现出来。