39. 组合总和
题目链接
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum/submissions/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题目分析
注意:candidates最小值为1。
纵向递归没有层数限制。可重复选取。
组合中:
一个集合求组合,需要startIndex。多个集合不需要。
class Solution {
private:
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex){
if(sum > target){//递归终止条件 只大于
return;
}
if(sum == target){//递归终止条件
res.push_back(path);
return;
}
for(int i = startIndex; i < candidates.size(); i++){
path.push_back(candidates[i]);
sum += candidates[i];
backtracking(candidates, target, sum, i);
//回溯
sum -= candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
res.clear();
path.clear();
backtracking(candidates, target, 0, 0);
return res;
}
};