LeetCode 39题：回溯算法解组合总和问题-北京尧图网络

1. 题目背景与核心需求LeetCode 39题组合总和是回溯算法领域的经典入门题目也是许多大厂技术面试的常考题型。这道题之所以重要是因为它完美展现了回溯算法的核心思想同时包含了组合类问题的典型特征。题目给出两个关键输入一个无重复元素的整数数组candidates一个目标整数target要求找出candidates中所有能使数字和为target的不同组合并以列表形式返回。这里的关键词是不同组合——即至少有一个数字的选取数量不同才被视为不同组合。例如[2,2,3]和[2,3,3]是不同的但[2,3]和[3,2]被视为相同题目允许以任意顺序返回。注意题目明确说明同一个数字可以无限制重复选取这是解题时需要特别注意的关键条件。比如candidates中有数字2target为4那么[2,2]就是一个合法的组合。2. 为什么选择回溯算法回溯算法特别适合解决这类组合搜索问题因为它能系统地遍历所有可能的解空间。我们可以把这个问题想象成一个决策树从第一个元素开始决定是否选择它如果选择可以继续选择因为允许重复计算当前和如果等于target就记录结果如果超过target就回溯剪枝尝试下一个元素回溯法的核心在于试探-回退机制这与我们现实生活中解决问题的思路非常相似——尝试一条路径如果走不通就退回来尝试其他可能性。3. 完整解法与代码实现3.1 基础回溯框架我们先来看一个基础的TypeScript实现function combinationSum(candidates: number[], target: number): number[][] { const result: number[][] []; const backtrack (start: number, path: number[], sum: number) { if (sum target) return; if (sum target) { result.push([...path]); return; } for (let i start; i candidates.length; i) { path.push(candidates[i]); backtrack(i, path, sum candidates[i]); path.pop(); } }; backtrack(0, [], 0); return result; };3.2 关键点解析start参数的作用这是避免重复组合的关键它确保我们总是从当前元素或之后的元素开始选择不会回头选择前面的元素这样就保证了组合中的元素是非递减的避免了[2,3]和[3,2]这样的重复递归调用递归时传递的是i而不是i1因为允许重复选择同一个元素每次递归都更新当前和(sum candidates[i])回溯操作path.pop()是关键的回溯步骤它撤销了上一步的选择让我们可以尝试其他可能性3.3 时间复杂度分析回溯算法的时间复杂度通常较高因为要遍历所有可能的组合。对于这个问题最坏情况下时间复杂度是O(N^(T/M1))其中N是candidates长度T是target值M是candidates中的最小值空间复杂度主要是递归栈的深度最坏是O(T/M)4. 优化与剪枝策略虽然题目说明组合数少于150个不需要考虑极端性能优化但良好的剪枝习惯对算法能力的提升很有帮助。4.1 排序预处理我们可以先对candidates进行排序candidates.sort((a, b) a - b);这样有两个好处可以更早地发现sum target的情况提前终止不必要的递归让结果中的组合保持有序更易读4.2 提前终止循环在排序的基础上我们可以在for循环中加入提前终止条件for (let i start; i candidates.length; i) { if (sum candidates[i] target) break; path.push(candidates[i]); backtrack(i, path, sum candidates[i]); path.pop(); }这样当发现当前元素加上去已经超过target时可以直接跳出循环因为后面的元素更大更不可能满足条件。5. 常见错误与调试技巧5.1 浅拷贝问题一个常见的错误是直接push path数组result.push(path); // 错误这样会导致结果集中的所有组合都指向同一个path引用最终所有组合都会变成空数组。正确的做法是创建path的副本result.push([...path]); // 正确5.2 重复组合问题另一个常见错误是忘记使用start参数导致生成重复组合for (let i 0; i candidates.length; i) { // 错误应该从start开始 // ... }5.3 调试技巧调试回溯算法时可以在递归函数开头添加日志console.log(start${start}, path[${path}], sum${sum});这样可以清晰地看到递归的调用过程和路径选择。6. 变种与扩展掌握了这道题的基本解法后我们可以尝试解决一些变种问题6.1 组合总和II (LeetCode 40)题目变化candidates中可能包含重复元素每个数字在每个组合中只能使用一次解法调整先排序递归时传递i1而不是i跳过重复元素6.2 组合总和III (LeetCode 216)题目变化只使用数字1-9每个数字最多使用一次组合长度为k组合总和为n解法调整数字范围固定为1-9需要同时检查组合长度和总和递归时传递i16.3 组合总和IV (LeetCode 377)题目变化考虑顺序不同的组合为不同组合实际上是求排列而非组合解法调整使用动态规划而非回溯dp[i]表示和为i的组合数7. 实际应用场景虽然这看起来像是一个纯算法题但回溯法的思想在很多实际场景中都有应用购物车优惠组合找出商品组合满足满减条件资源分配将有限资源分配给不同项目达到最优效果游戏设计解决谜题或寻找通关路径排班系统安排员工班次满足各种约束条件8. 个人实战经验分享在实际解决这类问题时我总结了几个有用的技巧画决策树在纸上画出前几层的递归调用直观理解回溯过程小规模测试先用简单的例子如candidates[2,3], target4手动推导预期结果边界检查特别注意空数组、target为0等边界情况性能预估对于较大的输入规模先估算可能的递归深度和组合数量一个特别有用的调试方法是给递归函数添加depth参数打印缩进const backtrack (start: number, path: number[], sum: number, depth: number) { console.log( .repeat(depth * 2) start${start}, path[${path}], sum${sum}); // ... } backtrack(0, [], 0, 0);这样可以看到递归的层级关系更容易发现逻辑错误。9. 与其他算法的对比回溯法不是解决这类问题的唯一方法我们来看几种替代方案9.1 动态规划对于组合总和问题动态规划也可以解决特别是LeetCode 377组合总和IV。DP的思路是function combinationSum4(nums: number[], target: number): number { const dp new Array(target 1).fill(0); dp[0] 1; for (let i 1; i target; i) { for (const num of nums) { if (i num) { dp[i] dp[i - num]; } } } return dp[target]; };9.2 迭代法我们也可以用栈来模拟递归过程实现迭代解法function combinationSumIterative(candidates: number[], target: number): number[][] { const result []; const stack []; candidates.sort((a, b) a - b); stack.push({ index: 0, path: [], sum: 0 }); while (stack.length) { const { index, path, sum } stack.pop(); if (sum target) { result.push([...path]); continue; } for (let i index; i candidates.length; i) { const newSum sum candidates[i]; if (newSum target) break; stack.push({ index: i, path: [...path, candidates[i]], sum: newSum }); } } return result; }9.3 算法选择考量选择算法时考虑回溯法适用于需要所有具体解的情况代码直观动态规划适用于只需要解的数量或最优解的情况迭代法避免递归栈溢出但代码稍复杂10. 进一步学习建议要真正掌握回溯算法我建议LeetCode回溯专题系统练习同类题目子集问题(78)排列问题(46)N皇后问题(51)可视化工具使用算法可视化网站观察回溯过程复杂度分析对每道回溯题进行时间和空间复杂度分析模板总结提炼回溯问题的通用模板如function backtrack(路径, 选择列表) { if (满足结束条件) { 结果.push(路径); return; } for (选择 of 选择列表) { 做选择; backtrack(路径, 选择列表); 撤销选择; } }实际项目应用尝试在个人项目中寻找可以使用回溯法解决的问题记住算法学习的关键不在于记住多少解法而在于培养解决问题的思维方式。每解决一个问题都思考为什么这个方法有效有哪些变种可能如何应用到实际问题中通过这样的刻意练习你会发现自己解决复杂问题的能力在不断提升。

LeetCode 39题：回溯算法解组合总和问题

相关推荐

2026年9月幕墙楼顶发光字厂家电话，字工场装配式工艺施工!

UniApp移动应用智能更新方案设计与实践

Java Web开发入门：Servlet环境搭建与实战指南

更多资讯

RoPE复数形式全解：旋转位置编码的几何意义与注意力分数推导

代码转流程图：开发者的逻辑可视化刚需工具指南

机械臂仿真链路：从URDF到Simscape再到S-Function的完整实践

Git SSH密钥配置、ed25519与多账号排查指南

Dev-C++ 5.11 安装配置与使用指南：从下载到调试的完整教程

IEPE传感器全解析：从压电效应到工程实践的振动测量指南

今日更新

AWS无服务器应用开发指南：从Lambda到SAM的架构与实践

SpringBoot+Vue人事系统实战：解决HR数据断点与事务一致性

MATLAB手写紧束缚模型计算石墨烯能带结构

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？