39.组合总和

        组合总和问题要求：给定一个数组，计算出所有能使数组元素之和等于目标值(targetSum)的子集组合。该问题与78. 子集 - 力扣（LeetCode）类似，区别在于需要在所有可能的子集中筛选出符合要求的组合。

解题思路可沿用78题的框架，通过递归实现选与不选的分类处理：

1. 选择当前元素：递归调用dfs(i, candidates, targetSum - candidates[i])
2. 不选当前元素：直接执行dfs(i, candidates, targetSum)

在回溯过程中需要注意：

• 当targetSum减至0时，表示找到一个有效组合，将其加入结果集(ans)
• 当targetSum小于0或已遍历完所有候选元素时，终止当前递归路径
• 需要回溯，如果当前元素不满足，需要尝试其他方案

class Solution {
public:vector<vector<int>> ans;vector<int> path;void dfs(int i,vector<int>& candidates,int target) {if (target == 0) {ans.push_back(path);return;}if (i == candidates.size() || target < 0) {return;}dfs(i + 1,candidates,target);path.push_back(candidates[i]);dfs(i,candidates,target - candidates[i]);path.pop_back();}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {dfs(0,candidates,target);return ans;}
};

剪枝优化：对数组排序，如果targetSum 小于当前元素，后面元素只会更大，不能满足targetSum为0，提前结束递归

class Solution {
public:vector<vector<int>> ans;vector<int> path;void dfs(int i,vector<int> &candidates,int target) {if(target == 0) {ans.push_back(path);return;}if (i == candidates.size() || target < candidates[i]) {return;}dfs(i + 1,candidates,target);path.push_back(candidates[i]);dfs(i,candidates,target - candidates[i]);path.pop_back();}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {ranges::sort(candidates);dfs(0,candidates,target);return ans;}
};