【练习】【回溯：组合：一个集合 元素可重复】力扣 39. 组合总和

题目

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数
target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7

输出：[[2,2,3],[7]]

解释：

2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。

7 也是一个候选， 7 = 7 。

仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8

输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1

输出: []

来源：力扣 39. 组合总和

---

思路（注意事项）

• const vector<int>& candidates

& 是引用符号。当一个函数参数被声明为引用类型时，函数内部使用的实际上是传入实参的别名，而不是实参的副本。这意味着对引用参数的修改会直接影响到原始的实参。引用传递避免了对象的复制，在处理大型对象时可以显著提高性能，减少内存开销。

• 在同一个集合中求组合，一定要有start（目的是为了避免重复组合）

---

纯代码

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

题解（加注释）

class Solution {
private:vector<int> path;         // 存储当前组合路径vector<vector<int>> ans;  // 存储所有符合条件的组合// 回溯函数// candidates: 候选数字集合（已排序）// target: 目标总和// sum: 当前路径元素和// start: 当前遍历起始索引（避免重复组合）void backtracking(vector<int> candidates, int target, int sum, int start) { // 注意这里 candidates 是值传递，会产生拷贝// 剪枝：当前和超过目标值，直接返回if (sum > target) return;// 终止条件：当前和等于目标值，记录结果if (sum == target) {ans.push_back(path);return;}// 遍历候选数字（从start开始，避免重复组合）for (int i = start; i < candidates.size() && target >= sum + candidates[i]; // 关键剪枝：提前终止无效分支i++) {sum += candidates[i];        // 选择当前数字path.push_back(candidates[i]);backtracking(candidates, target, sum, i); // 递归处理（注意传i而不是i+1，允许重复选择）sum -= candidates[i];        // 撤销选择path.pop_back();}}public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {// 关键优化：排序候选数组，方便后续剪枝sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0);return ans;}
};