题目描述：

给你一个无重复元素的整数数组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输出:[]

解题思路：

方法一：回溯 + 剪枝

核心思路：

把问题看成树形结构：

• 每一层选择一个数字

• 可以重复选同一个数字

• 当和等于target时，收集结果

• 当和大于target时，剪枝

关键：如何避免重复组合？

用start参数控制选择范围：

• 每次递归时，从start开始遍历

• 选了candidates[i]后，下一层从i开始（允许重复选当前数字）

• 但不能选i之前的数字（避免重复组合）

具体过程示例：

candidates = [2,3,6,7], target = 7

[] / / \ \ 2 3 6 7 /|\ |\ | 2 3 6 3 6 6 /|\ | | 2 3 6 3 6 6 | 2(和=8>7，剪枝) 有效路径: 2→2→3 (和=7) ✅ 7 (和=7) ✅

代码实现：

class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> result; vector<int> path; backtrack(candidates, target, 0, path, result); return result; } private: void backtrack(vector<int>& candidates, int target, int start, vector<int>& path, vector<vector<int>>& result) { // 终止条件：和等于 target if (target == 0) { result.push_back(path); return; } // 剪枝：和小于 0，直接返回 if (target < 0) return; // 从 start 开始遍历，避免重复组合 for (int i = start; i < candidates.size(); i++) { path.push_back(candidates[i]); // 选择 backtrack(candidates, target - candidates[i], i, path, result); // 递归，注意传 i 而不是 i+1 path.pop_back(); // 撤销 } } };

复杂度分析：

设n是候选数组长度，target是目标和。

更精确：时间复杂度与解的数量和递归深度有关，最坏情况为指数级。

关键细节：

1. 为什么递归时传i而不是i+1？

• 传i：允许重复选当前数字（如[2,2,3]）

• 传i+1：不允许重复选（如 40 题「组合总和 II」）

这是本题和 40 题的核心区别。

2. 为什么用start参数？

start控制当前层从哪个位置开始遍历，避免产生重复组合。

例子：candidates = [2,3],target = 5

• 如果不用start：[2,3]和[3,2]都会出现，重复

• 用start：选了 2 后，下一层只能从 2 开始（含 2），不能选 3 之前的

3. 为什么target < 0要返回？

因为和已经超过target，继续加只会更大，直接剪枝。

4. 排序优化（可选）

如果先对candidates排序，可以在target < candidates[i]时提前break：

sort(candidates.begin(), candidates.end()); // ... for (int i = start; i < candidates.size(); i++) { if (target < candidates[i]) break; // 后面的更大，直接结束 // ... }

方法二：动态规划（完全背包）

代码实现：

class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<vector<int>>> dp(target + 1); dp[0] = {{}}; for (int c : candidates) { for (int j = c; j <= target; j++) { for (auto& comb : dp[j - c]) { vector<int> newComb = comb; newComb.push_back(c); dp[j].push_back(newComb); } } } return dp[target]; } };

复杂度：时间 O(n × target × 解的数量)，空间 O(target × 解的数量)

缺点：需要存储所有中间结果，空间大。

两种方法对比：

总结：