力扣 39. 组合总和

题目来源：https://leetcode.cn/problems/combination-sum/description/

 

C++题解： 递归法。递归前对数组进行有序排序，可方便后续剪枝操作。

• 递归函数参数：定义两个全局变量，二维数组result存放结果集，数组path存放符合条件的结果。参数为集合candidates，和目标值target，已有元素和sum，及开始遍历的第ind个元素（注意，遍历时可以从ind开始，不用+1）；
• 递归终止条件：当sum大于target或sum等于target两种情况；
• 单层递归逻辑：更新sum值进行回溯。

class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracking(vector<int> candidates, int target, int sum, int ind) {if(sum > target) return;if(sum == target) {res.push_back(path); return;}for(int i = ind; i < candidates.size(); i++) {if(sum + candidates[i] > target) break;path.push_back(candidates[i]);backtracking(candidates, target, sum + candidates[i], i);path.pop_back();}return;}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());if(candidates[0] > target) return res;backtracking(candidates, target, 0, 0);return res;}
};