LeetCode 39. 组合总和——回溯中允许重复选取的实现细节
LeetCode 39. 组合总和——回溯中允许重复选取的实现细节
适读人群：Java初中级工程师、算法进阶学习者 | 阅读时长：约20分钟 | 难度：中等
开篇故事
组合总和这道题有一个让很多初学者困惑的地方：候选数组中的数可以无限次重复使用。这一点让"从哪里开始递归"变得微妙——如果每次递归都从 0 开始，会生成重复的组合（[2,3] 和 [3,2] 都被选到）；如果每次递归都从 start+1 开始，则重复使用当前数字就会被错误地跳过。
正确的答案是：递归时从 start（不是 start+1）开始，这样当前数字可以再次被选中（允许重复），但不会选择 start 之前的数字（避免重复组合）。
这个"从i而非i+1开始递归"的细节，是这道题与标准组合题的唯一代码差异，但背后的思维含量不小。今天我们把这个细节连同剪枝策略一起讲清楚。
一、题目解析
题目： 给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
示例：
- 输入：candidates = [2,3,6,7], target = 7
- 输出：[[2,2,3],[7]]
关键特点：
- 候选数组无重复元素。
- 每个元素可以被重复选取（与组合 LeetCode 77 的区别）。
- 结果是组合（无序），不是排列（有序）。
结果数量： 远不止 C(n,k) 那么简单，因为重复选取导致结果数量可能很大（取决于 candidates 和 target 的关系）。最坏情况（如 candidates=[1], target=大数）结果数量极大。
二、解法一：朴素回溯（理解重复选取的关键）
思路
关键差异：递归时下一层的 start 是 i（而非 i+1），允许再次选取 candidates[i]。
candidates = [2,3,6,7], target = 7
递归树（简化）：
选2: sum=2, 下次从index=0(2)开始
选2: sum=4, 下次从index=0(2)开始
选2: sum=6, 下次从index=0(2)开始
选2: sum=8 > 7, 剪枝
选3: sum=9 > 7, 剪枝
选3: sum=7, 记录[2,2,3]✓
选6: sum=10 > 7, 剪枝
选3: sum=5, 下次从index=1(3)开始
...
选6: sum=8 > 7, 剪枝
选3: sum=3, 下次从index=1(3)开始
...
选6: sum=6, 下次从index=2(6)开始
选6: sum=12 > 7, 剪枝
选7: sum=13 > 7, 剪枝
选7: sum=7, 记录[7]✓代码
import java.util.*;
public class Solution {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates); // 排序，方便后续剪枝
backtrack(candidates, target, 0, 0, new ArrayList<>());
return result;
}
private void backtrack(int[] candidates, int target, int start,
int currentSum, List<Integer> path) {
if (currentSum == target) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i < candidates.length; i++) {
// 剪枝：如果当前候选数已经超过了剩余目标，后续更大的数也不必尝试
if (currentSum + candidates[i] > target) break; // 注意是 break，不是 continue
path.add(candidates[i]);
// 关键：递归时从 i 开始（而非 i+1），允许重复使用 candidates[i]
backtrack(candidates, target, i, currentSum + candidates[i], path);
path.remove(path.size() - 1);
}
}
}关键细节：为什么 break 而不是 continue
排序后 candidates 是升序的，当 currentSum + candidates[i] > target 时，由于 candidates[i+1] > candidates[i]，后面所有的候选数都更大，加上去只会更超，所以可以直接 break 跳出整个循环，而不只是 continue 跳过当前。
这是一个重要的剪枝优化：提前排序后，用 break 替换 continue，可以将"每次超出就继续"变成"第一次超出就停止"。
复杂度分析
- 时间复杂度： O(n^(T/M))，其中 T 是目标值，M 是最小候选数。这是因为递归深度最多 T/M，每层最多 n 个选择。含剪枝后实际远小于此。
- 空间复杂度： O(T/M)，递归栈深度。
三、解法二：DFS+目标值减少（等价但更直观）
思路
把"当前和"换成"剩余目标"，逻辑更直观：每次选一个数，目标值减去这个数，递归处理剩余目标。当剩余目标为0时，找到一个解；当剩余目标为负时，剪枝。
代码
import java.util.*;
public class Solution_V2 {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
dfs(candidates, target, 0, new ArrayList<>());
return result;
}
private void dfs(int[] candidates, int remain, int start, List<Integer> path) {
if (remain == 0) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i < candidates.length; i++) {
if (candidates[i] > remain) break; // 剩余不够，后面更大，直接break
path.add(candidates[i]);
dfs(candidates, remain - candidates[i], i, path); // 注意：从 i 开始
path.remove(path.size() - 1);
}
}
}Mermaid 图：DFS递归树（[2,3,6,7], target=7）
复杂度分析
与解法一相同。
四、解法三：动态规划（理解问题的DP视角）
思路
虽然题目要求返回所有具体的组合，但我们可以先用DP思考"有多少种组合"，然后理解为什么回溯更适合返回具体结果。
定义 dp[i] = 目标值为 i 时的所有不同组合的列表。
转移：dp[i] = 对每个候选数 c，将 dp[i-c] 中的每个组合加上 c（注意去重：只取组合中最大值 >= c 的情况，或通过有序迭代避免重复）。
实现"避免重复组合"的关键：按候选数的顺序迭代，对 dp[i] 中的每个组合，只在末尾追加候选数（保证组合有序），这等价于"每次只扩展大于等于当前尾部元素的候选数"。
import java.util.*;
public class Solution_DP {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
// dp[i] 是目标值为 i 的所有组合
List<List<List<Integer>>> dp = new ArrayList<>();
for (int i = 0; i <= target; i++) dp.add(new ArrayList<>());
dp.get(0).add(new ArrayList<>()); // dp[0] = [空组合]
for (int i = 1; i <= target; i++) {
for (int c : candidates) {
if (c > i) break; // 候选数大于当前目标，跳过
for (List<Integer> combo : dp.get(i - c)) {
// 只在combo末尾追加 c（且c >= combo最后一个元素，保证有序不重复）
if (combo.isEmpty() || combo.get(combo.size() - 1) <= c) {
List<Integer> newCombo = new ArrayList<>(combo);
newCombo.add(c);
dp.get(i).add(newCombo);
}
}
}
}
return dp.get(target);
}
}复杂度分析
- 时间复杂度： 与回溯相同，O(n^(T/M))，因为DP也需要枚举所有组合。
- 空间复杂度： O(T × 结果总数)，存储所有dp状态，比回溯大得多。
- 实践建议： DP方式对于"返回具体组合"并不比回溯有优势，回溯更简洁且内存更优。但DP对于"统计组合数量"很高效（dp[i] 直接存数量而非列表）。
五、举一反三
与相关题目的对比
| 题目 | 重复选取 | 去重需求 | 递归起点 |
|---|---|---|---|
| LeetCode 77 组合 | 不允许 | 无 | i+1 |
| LeetCode 39 组合总和（本题） | 允许 | 无 | i（允许重复） |
| LeetCode 40 组合总和II | 不允许 | 需要 | i+1（+去重剪枝） |
记忆口诀：
- "从 i 开始"= 允许重复使用当前元素
- "从 i+1 开始"= 不允许重复使用当前元素
- 加 "i > start && nums[i] == nums[i-1] continue" = 含重复元素需去重
六、踩坑实录
坑一：递归时写 i+1 而不是 i
// 错误：不允许重复使用当前元素，[2,2,3]这类组合会漏掉
backtrack(candidates, target, i + 1, ...);
// 正确：允许重复使用当前元素
backtrack(candidates, target, i, ...);这是这道题最常见的错误，也是与 LeetCode 77 的唯一代码差异。
坑二：用 continue 而不是 break
// 低效：continue只跳过当前，继续检查更大的候选数（但更大的更不可能满足）
if (currentSum + candidates[i] > target) continue;
// 高效：break直接跳出，排序后更大的候选数必然也超出
if (currentSum + candidates[i] > target) break;这个错误不影响正确性，但会增加不必要的计算。
坑三：candidates 没有排序，break 不正确
如果不排序就用 break，可能会跳过后面更小的候选数。所以 Arrays.sort(candidates) 是使用 break 剪枝的前提条件。
坑四：path 添加的是 candidates[i] 而不是 i
有时候会写成 path.add(i) 而不是 path.add(candidates[i])，导致结果是下标而不是元素值。
七、总结
组合总和的核心是"允许重复选取"的实现方式：递归时下一层从 i（而不是 i+1）开始，这一行代码的修改，使得同一个元素可以被多次加入组合。
配合 Arrays.sort + break 剪枝，可以在当前候选数已经超出目标时，立即终止当前分支的探索，大幅减少无效计算。
| 解法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 回溯（传当前和） | O(n^(T/M)) | O(T/M) | 清晰直接 |
| DFS（传剩余目标） | O(n^(T/M)) | O(T/M) | 语义更直观 |
| 动态规划 | O(n^(T/M)) | 大 | 适合统计数量 |
补充深入讲解：允许重复选取的组合求和深度分析
允许重复选取带来的状态空间结构变化
与普通组合（不允许重复选取）相比，允许重复选取极大地改变了状态空间的结构。在不允许重复的情况下，每个元素最多被选一次，选了 k 个元素后递归深度最多为 n（总元素个数）。而在允许重复的情况下，理论上同一个元素可以被选无限次（受制于目标和 target 的限制），递归深度可以达到 target / min(candidates)。
以 candidates=[2]，target=100 为例，最深递归会选 50 个 2，递归深度 50。这意味着递归栈的深度取决于输入数值，而不只是数组大小，在某些极端情况下可能导致栈溢出。在实际题目中，candidates 的最小值和 target 的组合保证了递归深度在可接受范围内，但理解这个潜在问题有助于设计更健壮的解法。
排序预处理的多重价值
在组合总和的回溯中，对 candidates 预先排序有多重价值，不只是为了简化去重逻辑。
第一，排序使得剪枝成为可能。排序后，candidates 从小到大排列。在递归中，当 candidates[i] > remaining（当前剩余目标值），由于之后的元素更大，它们一定也 > remaining，可以直接 break（跳出循环），而不需要继续尝试。这个剪枝将回溯树的宽度从每层 n 个候选减少到有效候选数，效率提升显著。
第二，排序与 start 参数配合，自然避免了顺序不同但内容相同的重复组合。从 start 开始选，而不是从 0 开始，保证了结果中每个组合内元素的下标非递减，这对应了组合的"无序性"（[2,3] 和 [3,2] 是同一个组合）。
第三，排序后可以用二分查找快速找到"第一个大于 remaining 的元素下标"，作为循环的上界，进一步缩小候选范围。虽然在实践中这个优化不是必须的（直接判断 candidates[i] > remaining 就行），但在候选数组很长时，二分查找能减少不必要的循环次数。
组合总和的递归树分析
以 candidates=[2,3,6,7]，target=7 为例，分析递归树的结构。
每一层选一个候选值（允许重选），路径一直延伸到求和等于 target（记录结果）或超过 target（剪枝回退）。
不带剪枝的递归树会展开很多不必要的分支。带剪枝后，每次 candidates[i] > remaining 时 break，树被大幅裁剪。以 remaining=1 为例，candidates 最小值为 2，所有候选都 > 1，直接 break，该子树不产生任何有效叶节点，完全被剪掉。
组合总和的时间复杂度分析较为复杂，一般表示为 O(N^(T/M) × N)，其中 N 是候选个数，T 是 target，M 是 candidates 中的最小值。N^(T/M) 是递归树最大深度（T/M 层）和最大宽度（N 个分支）的乘积的上界，实际上因为剪枝，真实的树比这小得多。
与背包问题的联系
组合总和等价于完全背包问题的一种变体：物品集合为 candidates，每个物品可以无限次选取（完全背包），背包容量为 target，每个物品的重量等于其值，求恰好填满背包的所有方案（不是数量，而是方案本身）。
完全背包的动态规划解法可以求方案数：dp[i] 表示求和恰好为 i 的组合数量，dp[0]=1（空组合），dp[i] += dp[i-c] 对所有候选 c <= i。这是 O(target × N) 的解法，比枚举所有方案快得多。
但本题要求输出所有具体方案，不只是数量，所以 DP 不够用，必须回溯枚举。这是两种方法的本质区别：DP 计数高效，回溯枚举方案。
工程中的组合求和场景
组合总和在实际工程中有很多对应场景，最直观的是找零钱问题：给定一组面值的硬币（可重复使用），找出所有能组成特定金额的硬币组合方案。这是支付系统和收银台软件中的经典问题。
另一个应用是配置参数的总量约束：在系统配置中，多个可重复选取的组件各有自己的资源消耗量，系统有总资源上限，需要找出所有满足总量恰好等于上限的组件组合方案，用于容量规划和方案评估。
在化学分析中，质谱分析需要根据测量到的分子量，推断可能的分子结构（由若干已知原子/基团组成，每种可重复出现）。这也是组合总和的直接应用，只不过规模更大，通常需要配合剪枝和启发式方法处理。
理解了这些工程应用，可以帮助我们更好地把握算法的实用价值，也有助于在面试中用生动的例子解释算法的意义。
组合总和 I 的回溯框架与递归思维
组合总和的回溯框架代表了"允许重复选取的枚举"这一类问题的通用解法模式。区别于普通组合（每个元素最多选一次），允许重复选取的处理方式很简单：下一层递归的 start 参数不是 i+1，而是 i（可以继续选同一个元素）。
这个微小的变化（i+1 改为 i）使得同一个元素可以被无限次选取，但整体结构与普通组合回溯完全相同：选一个候选-递归-撤销选择。
理解了这个关键差异，后续遇到"允许重复"和"不允许重复"的组合问题，只需要在 start 参数传 i 还是 i+1 上做区分。这个细节是组合类回溯题中非常重要的知识点，面试时经常被考查。
排序之后的 break 剪枝（candidates[i] > remaining 时直接跳出循环）是组合总和剪枝的精华。break 比 continue 更高效：continue 只跳过当前候选，还会继续尝试后面更大的候选（同样会超出，都是无效的）；break 直接退出整个循环，一次性跳过所有更大的候选。这个 O(1) 的小优化，在递归深度较大时能积累出显著的性能提升。
组合总和的特殊情况分析
当 candidates 中只有一个元素，且 target 恰好是它的倍数时，只有一个结果：选若干个这个元素凑出 target。例如 candidates=[2]，target=6，唯一结果是 [2,2,2]。
当 candidates 中所有元素都大于 target 时，没有合法结果。排序后第一个元素就大于 target，for 循环第一次迭代就触发 break，结果为空列表，处理正确。
当 target 为 0 时（极少数题目变形），空集就是唯一的结果（空集的总和为 0）。标准代码的终止条件是 remaining == 0 时记录结果，这在 target==0 时会在第一次调用就记录空集，也能正确处理。
组合总和的学习路径定位
组合总和（LeetCode 39）在回溯学习路径中处于重要位置：它是第一道"允许重复选取"的回溯题，也是第一道需要"求和"约束的组合题。
从学习顺序来说，先掌握 LeetCode 77（普通组合，不允许重复，无求和约束），再学 LeetCode 39（允许重复，有求和约束），最后学 LeetCode 40（不允许重复，有求和约束，含重复元素需去重）。这个顺序由简到繁，每一步只引入一个新的复杂度，学习效率最高。
组合总和中最重要的一个细节是：递归调用时 start 传入 i（而不是 i+1），这允许同一元素被重复选取。在写代码时，这一行和普通组合的区别就是一个字符（i 还是 i+1），但含义完全不同。面试时被问到"允许重复和不允许重复的代码有什么区别"，能准确指出这一处差异并解释其含义，是对回溯理解深度的体现。
从技术角度来说，组合总和的 break 剪枝（candidates[i] > remaining 时跳出）和 LeetCode 77 的上界剪枝原理相同：都是"当前候选已经超出范围，后续候选只会更大，直接剪掉"。两道题的剪枝思想完全一致，这进一步说明了所有组合回溯题在底层逻辑上的统一性。
组合总和的核心在于允许重复选取，start 传 i 而不是 i+1 是与普通组合的唯一区别。