这道题又在之前的基础上进行了变形。递归是在一个集合里进行,但每次递归我们可以选择重复的数字,这代表递归时不需要缩小集合范围。但是组合的无序性仍要考虑,所以每一层for循环的起始值还是需要用变量控制。另外,我们可以事先对元素排个序,因为此题需要求和并与目标值进行比较。通过排序,我们就可以进行剪枝操作,提高效率。大家可以结合我下面的代码及详细注释理解。
代码及详细注释如下:
class Solution {
public:
//数组用来存放结果
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& candidates,int target,int sum,int start){
//剪枝
if(sum > target){
return;
}
//终止条件
if(sum == target){
result.push_back(path);
return;
}
//用start控制for循环
for(int i = start;i < candidates.size();i++){
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates,target,sum,i);//递归
//回溯
sum -= candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
backtracking(candidates,target,0,0);
return result;
}
};