学习算法时很多人都有同样一种体会看到题目解析觉得自己懂了关上题解自己写却无从下手。尤其是回溯和贪心这两类经典算法一个强调“把所有可能走一遍再回头”一个强调“每次选眼前最好的”思路完全不同却经常在同一个题目里出现。本文将围绕 LeetCode 刷题中的回溯 贪心展开先用决策树视角理解回溯的搜索空间再用局部最优理解贪心的选择策略最后通过几道高频题目演示从决策树到局部最优的实际应用。适合刚开始刷 LeetCode、算法基础还不太稳的读者也适合复习算法模板但希望摆脱死记硬背的同学。1. 为什么要从决策树开始理解回溯1.1 回溯的本质是搜索所有可行解回溯算法通常被解释为“深度优先搜索 状态回退”。这个说法没错但对新手来说还太抽象。换个角度每个回溯问题都可以看成在一棵决策树上的搜索。以 LeetCode 78. 子集为例。数组[1, 2, 3]的每个元素都有“选”和“不选”两种状态整棵决策树从空集开始第一层决定是否加入 1第二层决定是否加入 2第三层决定是否加入 3。叶子节点就是所有子集。[] / \ [1] [] / \ / \ [1,2] [1] [2] [] / \ / \ / \ / \ [1,2,3][1,2][1,3][1] [2,3][2] [3] []搜索过程就像在这棵树上做深度优先遍历沿着一条路径走到叶子记录一个结果然后回到上一个节点换一条没走过的分支继续走。这种“走到底再回头”的行为就是回溯名称的由来。1.2 回溯代码的三段式结构绝大多数回溯题解可以归纳成下面这个模板def backtrack(路径, 选择列表): if 满足结束条件: 结果.append(路径[:]) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择这套模板可以解决子集、排列、组合、分割、棋盘类等大量问题。关键在于三点路径是什么已经做出的选择。选择列表是什么当前还能做的选择。结束条件是什么什么时候把路径记录为答案。很多文章把这个模板当作万能公式但真正理解它需要结合决策树来看。递归调用的每一层对应树的一层for 循环遍历当前层所有可选分支进入递归表示沿着某个分支向下走撤销选择表示回到上一层继续尝试其他分支。1.3 剪枝不走到死路也知道不用走光有回溯还不够。如果不加任何优化很多题目的搜索空间会指数级爆炸。剪枝是在递归前判断某个分支不可能产生合法结果提前跳过。剪枝有两种常见思路可行性剪枝当前路径已经不满足题目约束继续走没有意义。最优性剪枝即使后面继续走也不可能比已找到的结果更好。例如 LeetCode 22. 括号生成。生成 n 对合法括号时如果当前右括号数量已经大于左括号数量那么这串括号前缀已经不合法后面的任何结果都不可能成为答案可以直接剪掉。2. 从决策树到回溯题解法两类高频题目2.1 子集问题路径和选择列表都不中断用 LeetCode 78 作为回溯入门题非常合适。它没有任何合法性约束只需要把每一步的路径都记到结果里。from typing import List class Solution: def subsets(self, nums: List[int]) - List[List[int]]: res [] path [] def backtrack(start: int, path: List[int]) - None: # 每一步的路径都是一个合法子集 res.append(path[:]) for i in range(start, len(nums)): path.append(nums[i]) backtrack(i 1, path) path.pop() backtrack(0, path) return res这里的start参数体现了组合类回溯的核心约束选过nums[i]之后下一次只能从i1开始选避免产生重复组合。如果把start写错可能会出现包含相同元素不同顺序的重复结果。运行结果s Solution() print(s.subsets([1, 2, 3])) # [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]为什么path.append之后再path.pop()因为path是共享列表递归返回后必须用手动 pop 把它恢复成进入递归前的状态。如果不恢复下一次 for 循环添加元素时path 里就会残留之前走过的分支导致结果错误。2.2 目标和问题带剪枝的 DFSLeetCode 494. 目标和是一个非常经典的 DFS 回溯题同时也是网络热词中反复出现的题目。题目的输入是一个非负整数数组和一个目标整数需要在每个数字前添加或-使得最终表达式的值等于目标值返回能构造出该表达式的方案数。决策树的角度很容易理解每个数字只能是正或负整棵树是二叉树深度为数组长度 n。凡是能走到叶子且总和等于 target 的路径都是一组可行解法。朴素 DFS 版本from typing import List class Solution: def findTargetSumWays(self, nums: List[int], target: int) - int: self.count 0 def dfs(index: int, current_sum: int) - None: if index len(nums): if current_sum target: self.count 1 return dfs(index 1, current_sum nums[index]) dfs(index 1, current_sum - nums[index]) dfs(0, 0) return self.count这段代码正确但遇到 n 较大时会超时因为时间复杂度是 O(2^n)。此时可以从两个方向优化。方向一记忆化搜索。dfs 的状态由(index, current_sum)决定同一个状态可能被多次计算因此可以用字典缓存。from functools import lru_cache class Solution: def findTargetSumWays(self, nums: List[int], target: int) - int: n len(nums) lru_cache(None) def dfs(index: int, current_sum: int) - int: if index n: return 1 if current_sum target else 0 return dfs(index 1, current_sum nums[index]) dfs(index 1, current_sum - nums[index]) return dfs(0, 0)方向二转化为背包问题。设数组所有元素和为 total添加负号的元素和为 neg则添加正号的元素和为 total - neg。题目要求(total - neg) - neg target total - 2 * neg target neg (total - target) / 2只有当total - target是非负偶数时才有解。此时问题变成从数组中选出若干元素使其和等于 neg 的方案数。这是标准 0/1 背包问题。from typing import List class Solution: def findTargetSumWays(self, nums: List[int], target: int) - int: total sum(nums) if (total - target) 0 or (total - target) % 2 ! 0: return 0 neg (total - target) // 2 dp [0] * (neg 1) dp[0] 1 for num in nums: for j in range(neg, num - 1, -1): dp[j] dp[j - num] return dp[neg]从 DFS 回溯到背包 DP 的转换是这一类枚举问题常见的优化思路。新手可以先掌握回溯解法再逐步理解动态规划如何将指数级搜索压缩成多项式时间。3. 贪心算法的核心是局部最优3.1 贪心和回溯的区别在哪回溯是在决策树上搜索所有路径最终选出符合要求的答案。贪心则完全不同它不搜索全部解空间而是每一步都选择一个当前看起来最优的决策并且不再回头。可以这样对比回溯所有路都走一遍走不通就回退。贪心每次只走当前感觉最好的那条路不回头也不考虑未来。贪心的优势是快劣势是可能得到错的答案。能否使用贪心取决于问题是否具备贪心选择性质和最优子结构。换句话说局部最优是否能推导出全局最优。很多初学者一听贪心就以为“每次取最大/最小就行”这种理解太粗暴。真正的贪心难点在于证明当前选择是安全的即这一步选了它之后一定存在一个全局最优解包含这个选择。面试中如果能说出这一层会比只会套模板好很多。3.2 贪心的经典题目选择LeetCode 455. 分发饼干可以作为贪心入门题。思路非常直接把孩子的胃口数组和饼干尺寸数组排序每次尽量用最小能满足胃口的饼干去喂孩子。from typing import List class Solution: def findContentChildren(self, g: List[int], s: List[int]) - int: g.sort() s.sort() i 0 j 0 while i len(g) and j len(s): if s[j] g[i]: i 1 j 1 return i为什么排序以后用当前最小能满足的饼干是安全的因为对某个胃口最小的孩子 g[i] 来说如果当前最小的饼干 s[j] 不能满足他那么后面更大的饼干也可能无法满足而更小的饼干已经排完或不存在。用尽可能小且能满足的饼干去满足当前孩子留下更大的饼干给别人这不会让整体结果变差。这个例子虽然简单却体现了贪心的核心证明方式交换论证。可以假设某个最优解不是选当前能用的最小满足饼干而是选了更大的饼干把两者交换结果不会变差。因此贪心选择是安全的。3.3 区间调度与重叠区间LeetCode 435. 无重叠区间是贪心高频题。题目给定多个区间需要移除最少数量的区间使剩余区间互不重叠。贪心策略按区间右端点升序排序每次选择右端点最小的区间并去掉所有与它重叠的区间那么最多能保留多少个不重叠区间。from typing import List class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) - int: if not intervals: return 0 intervals.sort(keylambda x: x[1]) keep 1 end intervals[0][1] for i in range(1, len(intervals)): if intervals[i][0] end: keep 1 end intervals[i][1] return len(intervals) - keep这里保留的是右端点尽可能小的区间。右端点越小给后面的区间留下的空间越多得到的结果就越优。贪心解法的正确性证明在面试中也很常见通常用反证法如果最优解中直接保留右端点最小的区间不会导致结果变差那么这个贪心选择安全。类似题目还有LeetCode 56. 合并区间。LeetCode 452. 用最少数量的箭引爆气球。LeetCode 55. 跳跃游戏。这几道题代码量不大但体现了排序后扫描区间的通用套路。4. 从决策树到局部最优用 LeetCode 406 综合体会LeetCode 406. 根据身高重建队列是一个很适合帮助理解贪心的问题。题目给出一组人的身高和前面身高不低于当前人身高的人数要求重新构造队列。一种通用思路是先按身高从高到低排序然后逐个插入。这么做效率高但很多人不理解为什么先排高个子就能成立。更深层的视角可以从决策树和逆序插入角度来建立直觉。先看贪心解法from typing import List class Solution: def reconstructQueue(self, people: List[List[int]]) - List[List[int]]: people.sort(keylambda x: (-x[0], x[1])) res [] for p in people: res.insert(p[1], p) return res这个解法非常短但需要解释清楚两个关键点第一同身高的人按 k 值升序排序。这样后插入的矮个子不会影响已经插入的高个子统计因为题目要求前面身高不低于自己的人矮个子站到高个子前面时不会增加高个子的计数。第二从高到低排序后每个个子较矮的人插入时当前结果里全是身高不低于他的人。因此他插入的位置 k 就是他在最终队列中的前面人数。此时直接按 k 作为下标插入即可。如果把这个过程想象成在决策树中做搜索每一个插入位置都代表一个分支但由于已经排好序我们可以确定唯一正确的位置不需要遍历所有可能这就是贪心在排序问题上的威力。如果对上面代码不放心可以先写一个回溯暴力解法把小规模数据喂进去验证再用贪心解法跑同一组数据对比结果。练习时建议用这种方式建立直觉而不是直接背结论。5. 回溯 贪心LeetCode 周赛常见组合思路LeetCode 周赛和热门 100 题中回溯与贪心经常出现在不同题目中但偶尔也会在同一道题里配合使用。典型的场景是问题看起来是搜索/枚举但部分子问题可以用贪心加速。使用回溯枚举所有可能组合再在回溯中通过贪心剪枝让搜索范围迅速缩小。先用贪心想到一个可行边界然后在边界附近用回溯精确求解。以 LeetCode 40. 组合总和 II 为例。题目要求从数组中找出所有和为 target 的组合每个数字在每个组合中只能使用一次。如果数组很大直接回溯会产生很多重复搜索。此时排序 去重剪枝是标准做法。from typing import List class Solution: def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]: candidates.sort() res [] path [] def backtrack(start: int, remain: int) - None: if remain 0: res.append(path[:]) return if remain 0: return for i in range(start, len(candidates)): if i start and candidates[i] candidates[i - 1]: continue if candidates[i] remain: break path.append(candidates[i]) backtrack(i 1, remain - candidates[i]) path.pop() backtrack(0, target) return res这里有两个优化排序后如果candidates[i] remain说明后续元素都大于当前元素不可能凑出 remain直接 break。这种策略属于贪心思路下的剪枝。跳过同一层相同元素避免了重复组合。注意条件i start代表的是同一层跳过重复而不是跨层跳过。这个例子说明回溯和贪心不是对立关系而是可以协作的回溯负责枚举可能的分支贪心负责在枚举之前排除掉明显不可能的分支。再看一道带“反悔”思想的题目。LeetCode 种树这类问题中贪心选择有时会出错因此需要加入“反悔”结构允许之前的选择被替换。这类算法通常叫反悔贪心常见于带权调度类问题。反悔贪心的实现思路是用堆维护当前选择的代价。当新元素比堆中的最优元素更适合时弹出堆顶元素并放入新元素使得总收益不会被一个局部最优选择锁死。这类题目适合在掌握基本贪心后再深入学习因为它的“贪心选择 堆替换”本质上等于在一个决策树上保留多个候选分支只是用堆统一管理候选集。6. 回溯与贪心的几个易错场景6.1 回溯中忘记撤销选择出现错乱结果时先检查是不是没有 pop 或者在递归前修改了传入状态。正确做法是尽量让递归参数不依赖可变对象。如果必须共享 path记得在递归返回后恢复。6.2 贪心不一定适用于所有最值问题背包问题不能直接用贪心因为物品不可分割时不能保证“单位价值最高优先”产生全局最优解。反例很简单背包容量为 10物品 A 重量 6 价值 8物品 B 重量 5 价值 6物品 C 重量 5 价值 6。若按单位价值贪心会先选 A剩余容量只能放一个 B 或 C总价值 14但最优解是选 B 和 C总价值 12。这里单位价值贪心得到 14 反而大于最优需要重新设计反例例如容量 8物品 A 重量 7 价值 10B 重量 4 价值 6C 重量 4 价值 6。按单位价值 A 最高先选 A 后剩余容量 1无法放 B/C总价值 10最优解是 BC总价值 12。这个例子说明背包不能简单贪心而应该用动态规划或回溯搜索。很多初学者把背包问题当作贪心题结果在测试用例上翻车。正确的做法是先判断最优子结构是否满足不行就回溯或动态规划。6.3 回溯超时但不知道怎么优化回溯优化优先级建议先看是否有重复状态的递归调用考虑记忆化。再看能否通过排序和剪枝提前终止。最后检查能否把组合/排列问题转换成背包等 DP 模型。不要一上来就写复杂状态压缩先把基础剪枝做好。7. 架构一套简单的问题识别方法在 LeetCode 刷题时如果看到类似表述可以先做判断。如果题目要求“列出所有可能解”“计算方案数”“枚举所有排列组合”那很可能要用到回溯。代表题目包括全排列、子集、组合总和、分割回文串、N 皇后、目标和的 dfs 版本。如果题目要求“求最大/最小且每一步可以用一个显然的策略确定选择不需要枚举全部状态”那可能能用贪心。代表题目包括分发饼干、跳跃游戏、无重叠区间、用最少数量的箭引爆气球。如果题目是“求最值但要满足复杂的约束”那通常是动态规划或回溯 剪枝。这个判断标准当然不是百分之百准确但可以作为一个刷题初期的思考入口。8. 刷题方法和学习路径建议8.1 先画决策树再写代码遇到回溯题在草稿纸上画出小规模输入的决策树。画出后代码里的递归参数、终止条件、剪枝条件都会变得很直观。例如 LeetCode 22 括号生成如果 n2可以画出以下路径start level 1: ( level 2: (( 或 () level 3: 到 (( 时只能加 ) 到 () 时可以加 ( ...画完后会发现左括号数量小于 n 时总能加左括号右括号数量小于左括号时才能加右括号。这个约束是画图时自然浮现的比直接背代码记得牢。8.2 贪心练习要关注证明贪心题的代码往往很短容易让人以为“只要背下套路就行”。实际上LeetCode 周赛里的难题难点都在于怎么证明一个看似简单的选择不会丢最优解。常见证明方式交换论证把任意最优解调整成贪心解证明结果不会变差。反证法假设贪心选择不在某个最优解中构造包含贪心选择的新最优解。归纳证明证明每一步贪心选择之后剩余子问题仍然可以用相同策略解决。练习建议是不要只 AC 就结束可以试着用文字解释一次为什么贪心能 AC。8.3 从 LeetCode 热门 100 题开始练热门 100 题里适合练习回溯和贪心的题目比较集中。可以先做子集、全排列、组合总和、括号生成、单词搜索再做跳跃游戏、区间合并、股票买卖、分发糖果、救生艇等。每一类题目做完之后归纳出自己的一页笔记把代码模板和相关题目放在一起后续复习时效率会高很多。8.4 不建议把模板当作万能解网上有很多“回溯万能模板”“贪心套路总结”看可以但不能只会背模板。如果面试官换一个隐藏约束的问题死记模板很容易识别不出真正的难度。更好的做法是拿到问题后先画样例再进行小规模推理最后才写代码。模板的作用是约束代码结构但算法思路必须由你对问题结构的理解来驱动。9. 结合算法思想的工程启示算法题和应用开发看似距离很远但回溯与贪心背后的思维方式在工程中非常有用。回溯的本质是系统化枚举可能方案适合在配置项组合校验、规则引擎冲突检测、权限路径匹配等场景中使用。工程代码里如果需要对有限的选项组合做穷举回溯往往比多层 for 循环更清晰。贪心的本质是在资源有限时寻找近似最优解。例如云服务器资源调度、缓存淘汰策略、CDN 节点选择、任务队列排班等场景都会用到贪心近似策略。完全精确的最优解可能计算量太大“每一步挑当前最合理”的策略即使不是数学最优也往往能跑得很快且表现足够好。因此在刷 LeetCode 时可以顺便培养一种能力把决策树和局部最优思维转译成日常业务里的方案设计能力。10. 常见报错与调试方式回溯和贪心代码出错时常见错误并不难定位。问题现象常见原因解决思路结果是重复的列表回溯中忘记跳过同一层相同元素排序后在 for 循环里加去重条件path 最终为空结果中保存的是 path 引用递归后 path 被清理保存时使用 path[:] 或 path.copy()递归超出最大深度结束条件写错递归无法退出检查 base case 是否覆盖所有边界代码超时搜索空间太大、缺少剪枝尝试记忆化搜索、状态压缩或转换为动态规划贪心结果不通过问题不具备贪心选择性质使用动态规划或回溯验证下标越界排序后访问intervals[i1]等越界位置在循环中加长度判断排在第一个的结果重复问题是很多新手刷“组合总和 II”时最先遇到的现象。看到重复结果后不要盲目在结果里去重因为这样复杂度很高。正确做法是在递归树的同一层跳过重复元素从源头上避免重复分支。如果你是使用 Python 刷题调试回溯还可以在 backtrack 函数入口加打印输出当前 path 和 start。看到递归调用过程后很多逻辑错误会立刻清晰。11. 写在最后回溯和贪心是 LeetCode 基础算法里非常值得花时间吃透的两个方向。回溯强调从决策树出发把枚举过程结构化贪心强调在正确的排序/选择策略下用局部最优推导全局最优。刷题时建议不要贪多每一题都尝试做三件事第一画出小规模的决策树第二写出递归状态和转移第三思考是否有比回溯更高效的思路比如贪心、记忆化、动态规划。这样坚持几十题之后会发现面对新题时的第一反应不是背模板而是判断它属于哪种搜索结构能不能贪心不能贪心时怎么剪枝。LeetCode 周赛和热门 100 题中的相关题目都可以作为练习题。如果暂时 AC 不了也不要着急先看题解理解结构再自己从决策树开始推导远比直接抄代码更能加深记忆。希望这篇笔记能帮你少走一些弯路。如果有收获也可以收藏起来后面复习到回溯和贪心时再翻一翻。