Java版LeetCode热题100之组合总和：回溯算法与剪枝优化的深度解析

Java版LeetCode热题100之组合总和：回溯算法与剪枝优化的深度解析

摘要：本文将深入剖析 LeetCode 热题 100 中的经典回溯问题——组合总和（Combination Sum）。我们将从题目出发，系统讲解回溯算法的核心思想、递归结构设计，并重点探讨剪枝优化策略。文章提供完整可运行的 Java 实现，涵盖时间/空间复杂度分析、常见面试问题、实际应用场景、相关题目推荐等模块，帮助读者不仅掌握解题技巧，更能理解其背后的算法思想与工程价值。

一、原题回顾

题目名称：组合总和
题目编号：LeetCode 39
难度等级：中等

题目描述

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

• 同一个数字可以无限制重复被选取
• 如果至少一个数字的被选数量不同，则两种组合是不同的
• 保证和为 target 的不同组合数少于 150 个

示例

示例 1： 输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 解释：2 + 2 + 3 = 7，7 = 7 示例 2： 输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]] 示例 3： 输入: candidates = [2], target = 1 输出: []

提示

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates的所有元素互不相同
• 1 <= target <= 40

二、原题分析

本题是一个经典的完全背包问题的变种，但要求输出所有可行解而非最优解数量。关键特征：

• 元素可重复使用→ 完全背包特性
• 无重复元素→ 无需去重处理
• 组合而非排列→[2,2,3]和[2,3,2]视为同一组合
• 目标明确→ 和恰好等于target

由于target ≤ 40且candidates[i] ≥ 2，最大递归深度为40/2 = 20，属于可接受范围，适合使用回溯法（Backtracking）。

💡关键洞察：为了避免生成重复组合（如[2,3,2]），我们需要按顺序选择元素，即一旦跳过某个元素，后续就不能再选择它。

三、答案构思

3.1 回溯法的核心思想

对每个元素，我们有两个选择：

1. 跳过当前元素→ 处理下一个元素
2. 选择当前元素→ 仍可继续选择当前元素（因可重复）

通过维护一个起始索引（start index），确保组合按非递减顺序生成，从而避免重复。

3.2 算法步骤

1. 排序（可选但推荐）：便于剪枝优化
2. 回溯函数：
   • 结束条件1：target == 0→ 找到有效组合
   • 结束条件2：target < 0或idx >= candidates.length→ 无效路径
   • 选择1：跳过当前元素，递归idx + 1
   • 选择2：选择当前元素（若target >= candidates[idx]），递归idx（保持索引不变）

3.3 剪枝优化的重要性

• 排序后剪枝：若candidates[idx] > target，则后续所有元素都更大，可直接终止
• 提前终止：减少无效递归调用

四、完整答案（Java 实现）

4.1 基础版（官方题解）

classSolution{publicList<List<Integer>>combinationSum(int[]candidates,inttarget){List<List<Integer>>result=newArrayList<>();List<Integer>path=newArrayList<>();backtrack(candidates,target,0,path,result);returnresult;}privatevoidbacktrack(int[]candidates,inttarget,intstart,List<Integer>path,List<List<Integer>>result){// 找到有效组合if(target==0){result.add(newArrayList<>(path));return;}// 遍历从 start 开始的元素for(inti=start;i<candidates.length;i++){// 剪枝：当前元素已超过剩余目标if(candidates[i]>target){break;}// 做选择path.add(candidates[i]);// 递归：仍从 i 开始（允许重复）backtrack(candidates,target-candidates[i],i,path,result);// 撤销选择path.remove(path.size()-1);}}}

4.2 优化版（预排序 + 强剪枝）

classSolution{publicList<List<Integer>>combinationSum(int[]candidates,inttarget){// 排序便于剪枝Arrays.sort(candidates);List<List<Integer>>result=newArrayList<>();backtrack(candidates,target,0,newArrayList<>(),result);returnresult;}privatevoidbacktrack(int[]candidates,inttarget,intstart,List<Integer>path,List<List<Integer>>result){if(target==0){result.add(newArrayList<>(path));return;}for(inti=start;i<candidates.length;i++){// 强剪枝：当前元素过大，后续更不可能if(candidates[i]>target){break;}path.add(candidates[i]);backtrack(candidates,target-candidates[i],i,path,result);path.remove(path.size()-1);}}}

✅关键改进：

1. 预排序：使剪枝更有效
2. for 循环替代双递归：代码更简洁，逻辑更清晰
3. 统一剪枝条件：在循环内判断

五、代码分析

5.1 为什么用start参数？

• 防止重复组合：确保组合按非递减顺序生成
• 示例：candidates = [2,3,6,7]
  • 先选 2，后续可选 2,3,6,7
  • 跳过 2 后选 3，后续只能选 3,6,7（不能再选 2）
• 效果：天然避免[2,3,2]这类重复

5.2 递归树结构

以candidates = [2,3,6,7],target = 7为例：

[] / | | \ [2][3][6][7] /| | | [2,2][2,3] [7]✓ / | | [2,2,2][2,2,3]✓ | [2,2,2,2]✗ (target=-1)

• ✓：有效组合
• ✗：无效路径（target < 0）
• 每层只考虑从当前索引开始的元素

5.3 剪枝机制详解

无排序的剪枝

if(candidates[i]>target)continue;

• 只跳过当前元素，但后续可能有更小元素（因未排序）

有排序的强剪枝

Arrays.sort(candidates);// ...if(candidates[i]>target)break;

• 因数组已排序，candidates[i] > target意味着所有后续元素都 > target
• 可直接break终止整个循环

📌性能对比：对于candidates = [7,6,3,2],target = 7

• 无排序：需检查所有元素
• 有排序：[2,3,6,7]，当i=3时7>7?不成立，但若target=5，则6>5时可break

5.4 深拷贝的重要性

result.add(newArrayList<>(path));

• 必须创建副本，否则所有组合将指向同一个path对象
• 最终结果会全部等于最后一次path的状态

六、时间复杂度与空间复杂度分析

6.1 时间复杂度：O(S)

• S：所有可行解的长度之和
• 理论最坏情况：O(N^(T/M))，其中
  • N = candidates.length
  • T = target
  • M = min(candidates)
• 实际运行：远小于理论值，因剪枝大幅减少搜索空间

💡举例：candidates = [2],target = 40

• 只有一个解：[2,2,...,2]（20个2）
• 时间复杂度 O(20) = O(target)

6.2 空间复杂度：O(target)

• 递归栈深度：最坏情况下为target / min(candidates)
  • 例如min=2,target=40→ 深度 20
• 路径存储：O(target)（当前组合的最大长度）
• 结果集空间：O(S)，但通常不计入空间复杂度

📌标准答案的空间复杂度为 O(target)（仅考虑算法运行所需额外空间）。

七、常见问题解答（FAQ）

Q1: 为什么不用动态规划？

答：DP 适合求解的数量或最优解，但本题要求输出所有解：

• DP 无法记录具体组合
• 回溯天然适合枚举所有解

Q2: 能否用 BFS 实现？

答：可以，但效率较低：

• 队列存储(current_sum, current_combination, start_index)
• 每次扩展：尝试添加candidates[i]（i ≥ start_index）
• 缺点：内存开销大（需存储中间组合）

Q3: 如果 candidates 有重复元素怎么办？

答：这是LeetCode 40（组合总和 II）：

• 需先排序
• 在“跳过”分支后，跳过所有重复元素
• 关键代码：

  if(i>start&&candidates[i]==candidates[i-1])continue;

Q4: 如何限制每个元素的使用次数？

答：这是0-1 背包或多重背包问题：

• 0-1 背包：每个元素最多用 1 次 → 递归时start = i+1
• 多重背包：每个元素有使用上限 → 需额外参数记录使用次数

八、优化思路

8.1 排序 + 强剪枝（已实现）

• 预排序：Arrays.sort(candidates)
• 循环内 break：if (candidates[i] > target) break;

8.2 预计算最小值

提前终止明显无效的输入：

intmin=Arrays.stream(candidates).min().getAsInt();if(min>target)returnresult;// 无解

但target ≥ 1且candidates[i] ≥ 2，此优化收益有限。

8.3 使用数组代替 List（微优化）

减少对象创建：

privatevoidbacktrack(int[]candidates,inttarget,intstart,int[]path,intlen,List<List<Integer>>result){if(target==0){result.add(Arrays.stream(path,0,len).boxed().collect(Collectors.toList()));return;}for(inti=start;i<candidates.length;i++){if(candidates[i]>target)break;path[len]=candidates[i];backtrack(candidates,target-candidates[i],i,path,len+1,result);}}

调用：

int[]path=newint[target];// 最大可能长度backtrack(candidates,target,0,path,0,result);

优点：无 add/remove 开销
缺点：代码复杂，且需转换为 List

8.4 尾递归优化？不可行

• Java 不支持尾递归优化
• 且本题非尾递归（递归后还有操作）

九、数据结构与算法基础知识点回顾

9.1 回溯算法核心

• 三要素：
  1. 路径：已做出的选择（当前组合）
  2. 选择列表：当前可做的选择（从 start 开始的元素）
  3. 结束条件：找到有效解或确定无解
• 模板：

  voidbacktrack(路径,选择列表){if(满足结束条件){result.add(路径);return;}for(选择:选择列表){做选择;backtrack(路径,新选择列表);撤销选择;}}

9.2 完全背包 vs 0-1 背包

9.3 剪枝（Pruning）技术

• 定义：提前终止无效搜索分支
• 类型：
  • 可行性剪枝：当前路径已不可能达到目标（如target < 0）
  • 最优性剪枝：当前路径已不如已知最优解（本题不适用）
  • 重复性剪枝：避免生成重复解（通过start参数）

9.4 组合 vs 排列

💡组合问题的关键：通过起始索引控制选择顺序，避免重复。

十、面试官提问环节（模拟）

Q1: 请手写组合总和，并解释如何避免重复组合。

答：（写出优化版代码后解释）

• 我使用start参数控制选择范围
• 每次递归只考虑从当前索引开始的元素
• 这样确保组合按非递减顺序生成，天然避免重复
• 例如：先选 2 后可选 2,3,6,7；跳过 2 后选 3，就不再能选 2

Q2: 时间复杂度是多少？能否优化？

答：

• 时间复杂度 O(S)，S 为所有解的长度之和
• 无法优化渐进复杂度，因为必须输出所有解
• 但可通过排序+剪枝大幅减少常数因子
• 例如：排序后，一旦candidates[i] > target就终止循环

Q3: 如果 candidates 包含负数怎么办？

答：问题会变得复杂：

• 可能存在无限解（如[-1,1],target=0→[-1,1],[-1,-1,1,1], …）
• 需要额外约束（如限制组合长度）
• 或题目保证无负数（本题已保证）

Q4: 如何修改代码以限制每个元素最多使用 k 次？

答：

• 方法1：传递使用次数数组，在递归时检查
• 方法2：展开 candidates（如元素 x 最多用 k 次 → 添加 k 个 x）
• 方法3：在递归参数中加入剩余使用次数

// 方法1示例privatevoidbacktrack(int[]candidates,int[]counts,inttarget,intstart,List<Integer>path,List<List<Integer>>result){if(target==0){/* ... */}for(inti=start;i<candidates.length;i++){if(counts[i]>0&&candidates[i]<=target){path.add(candidates[i]);counts[i]--;backtrack(candidates,counts,target-candidates[i],i,path,result);counts[i]++;path.remove(path.size()-1);}}}

Q5: 回溯中的“撤销选择”为什么重要？

答：因为回溯是共享状态的递归。

• 若不撤销，后续分支会基于错误的状态计算
• 例如：第一次选择 2 后未移除，第二次选择 3 时路径变成[2,3]而非[3]
• 导致结果错误或重复

十一、这道算法题在实际开发中的应用

11.1 货币找零问题

• 给定面额[1,5,10,25]，找零target分
• 求所有可能的找零组合
• 注意：实际找零通常求最少硬币数（用 DP），但某些场景需枚举所有方案

11.2 资源分配

• 服务器有多种资源配置方案
• 客户需求为target单位资源
• 枚举所有满足需求的配置组合

11.3 测试用例生成

• API 参数有多个选项，每个选项可重复使用
• 生成所有参数组合，使总“权重”等于目标值

11.4 游戏开发

• 技能组合：不同技能消耗不同 MP，总 MP 为target
• 枚举所有可行的技能释放序列（组合）

11.5 财务规划

• 投资组合：不同产品投资额固定，总预算为target
• 枚举所有投资方案

💡 虽然实际中很少直接枚举所有组合（因数量可能爆炸），但组合优化思想广泛应用于各种资源分配问题。

十二、相关题目推荐

学习路径建议：

1. 掌握本题（完全背包 + 回溯）
2. → 40（去重技巧）
3. → 216（加约束条件）
4. → 377（排列 vs 组合）
5. → 518/322（DP 解法对比）

十三、总结与延伸

13.1 核心收获

• 组合总和是完全背包问题的回溯解法
• start参数是避免重复组合的关键
• 排序 + 剪枝能大幅提升性能
• 时间复杂度由输出规模决定，无法优化渐进复杂度

13.2 延伸思考

动态规划能否输出所有解？

• 理论上可以，但需额外存储路径信息
• 空间开销巨大：每个状态需存储所有到达该状态的路径
• 实际不可行：本题更适合回溯

支持小数或浮点数？

• 不推荐：浮点精度问题会导致target == 0判断失效
• 解决方案：使用误差范围Math.abs(target) < 1e-6
• 但题目保证整数，无需考虑

并行化？

• 困难：回溯的决策树难以分割
• 可能方案：对第一个元素的选择并行处理
• 但小数据量下 overhead 大于收益

13.3 学习建议

1. 动手实现：手写回溯模板（路径/选择/结束条件）
2. 理解剪枝：排序如何帮助剪枝
3. 区分组合/排列：通过起始索引控制
4. 刷相关题：巩固背包问题的不同变种
5. 思考 DP vs 回溯：何时用哪种方法

结语：组合总和问题完美展示了回溯算法在组合优化中的强大能力。通过巧妙的剪枝和状态控制，我们不仅能高效解决问题，还能避免常见的陷阱（如重复组合）。掌握它，不仅是为了解决这一道题，更是为了建立起解决更复杂资源分配问题的能力。希望本文能助你在算法之路上走得更远！