刷 LeetCode 的人在回溯和贪心这两种算法上容易走两个极端。一种是把回溯模板背得很熟组合、排列、子集、全都能硬套代码另一种是被贪心的简洁吸引遇到最值题就猜一个局部最优策略提交通过就认为自己掌握了。这两种做法都能解决眼前的题目也很容易让人产生“学会”的错觉。真正应该先理解的是回溯和贪心并没有那么割裂它们可以放在同一棵“决策树”上理解。这篇内容从一个常见提问出发小白刷 LeetCode为什么总说“遇到回溯先画树遇到贪心先证明”因为回溯本质上是在深度优先遍历一棵决策树贪心则是每一步只沿着一条“当前看起来最优”的分支往下走。理解了树再看模板、看剪枝、看局部最优和全局最优的关系才不会变成背题机器。1. 回溯和贪心其实是在同一棵决策树上工作1.1 算法题里的“决策树”不是机器学习里的决策树很多读者一听到“决策树”会先联想到机器学习里的分类树。这里说的决策树不是训练模型而是一种描述解题过程的状态树。在一道算法题中可以把“做选择的过程”画成一棵树。树根是初始状态每一层对应一次选择每个节点是一个状态节点下面的分叉代表下一步可以做的不同选择。从根节点走到某个叶子节点就得到一条完整的路径也就是一个候选答案。例如全排列问题输入[1, 2, 3]第一次可以选择以 1、2、3 哪一个开头第二次从剩余两个数字中选择最后一次选择最后一个数字这棵树总共有三层决策每个叶子节点都是一个长度为 3 的完整排列。回溯要做的就是从根开始把所有叶子都试一遍。1.2 回溯深度优先遍历决策树回溯算法的标准描述是“深度优先搜索 状态撤销”。它做三件事做选择在当前状态选择一个候选项进入下一层。递归继续做下一次选择直到满足终止条件。撤销选择回到上一层换另一个候选分支继续尝试。撤销这一步是回溯最容易出错的地方。因为多个分支会共享同一个状态变量。如果不把刚才的选择撤销掉下一次遍历到这个变量时状态就会被上一次分支污染。全排列、组合、子集、括号生成、N 皇后、数独等题目都可以还原成这种“决策树搜索”。回溯解决的是这类问题的通法它不聪明但很可靠代价是搜索空间可能非常大。1.3 贪心每一步只沿一条分支走到底贪心则走了另一条路线。它也在决策树上选择但不会把整棵树都搜完而是每一步都根据当前状态选择一个“局部最优”的分支然后继续往下走不再后悔。这种做法的优势是快只需一层一层地选下去。但它的致命弱点是局部最优的选择未必能导向全局最优。LeetCode 中贪心题目的真正难点从来不是“想出贪心策略”而是“证明这个策略每一步都不会错”。如果只凭感觉写一个贪心很容易在隐藏用例上翻车。1.4 为什么先看树再记模板很多教程会把回溯代码简化为“模板”然后让你反复练习。模板本身没有错但模板遮住了背后最重要的东西你在遍历一颗什么样的树每一层的可选集合是怎么变化的。同样贪心的代码通常很短短到你看不出任何风险。只有回到决策树上问“我跳过哪些分支为什么这些分支不可能比当前选择更好”才能真正判断这道题能不能用贪心。下面选择三道经典题把这段关系串起来LeetCode 46 全排列用回溯完整遍历决策树。LeetCode 55 跳跃游戏用贪心只走一条路径。LeetCode 322 零钱兑换用反例说明贪心为什么会错。2. LeetCode 46 全排列从决策树到回溯代码2.1 题目样例和最小规模题目要求是给定一个没有重复元素的整数数组nums返回所有可能的全排列。输入nums [1,2,3] 输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]题目本身不复杂但它非常适合用来理解决策树每个位置是一个“选择点”。已经用过的数字不能再出现在后面的位置。所有数字都选完才能得到一个合法排列。建议先不要急着写代码把这个三元素数组的决策树画出来。第一层有三种分支第二层每个分支下有两种分支第三层只有一个分支。当数组长度为 n 时叶子节点数是n!这就是全排列问题的搜索空间。2.2 先确定状态需要记录哪些信息要遍历这棵树至少要记录两类信息当前已经选出的路径用path保存。哪些数字已经被用过用used布尔数组保存。只要知道这两点就可以确定下一步可选集合。比如当path是[1]时used中 1 已经为True下一层只能从 2 和 3 中选择。这里要注意一个容易混淆的点全排列是“位置敏感”的所以需要使用used标记元素是否被使用而组合、子集类问题通常不需要used而是用start下标控制起点从而避免重复组合。两者适用的树形结构不同。2.3 Python 回溯代码选择、递归、撤销from typing import List class Solution: def permute(self, nums: List[int]) - List[List[int]]: res [] path [] used [False] * len(nums) def dfs(): # 终止条件路径长度等于数组长度 if len(path) len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue # 做选择 used[i] True path.append(nums[i]) # 递归进入下一层 dfs() # 撤销选择 path.pop() used[i] False dfs() return res这段代码可以原样放到 LeetCode 46 的环境里执行。即使没用过 Python也可以试着把注释读一遍重点观察三个动作的顺序。实际执行过程如下从根节点开始path为空。第一层循环选择1标记used[0] True。递归进入第二层循环跳过已用数字1选择2。第三层只剩3此时len(path) 3保存结果并返回。返回后撤销3和2继续尝试其他分支。 的作用将在下一节专门解释。2.4 为什么保存结果时要拷贝 path这是回溯新手几乎都会踩的坑。path是一个列表对象在递归过程中会不断被修改。如果把path直接放进res保存的并不是某个状态的快照而是同一个对象的引用。当递归返回上一层并执行path.pop()时这个对象里的内容就变了。最终res里所有的“排列”都会变成同样的空列表或者同样的最后一次状态。解决办法是写入副本res.append(path[:])path[:]会复制当前列表内容生成一个新的列表对象。这样即使原来的path继续变化结果列表里保存的值也不会受影响。理解这一步比背诵模板更关键。只要弄清了“可变对象共享”的问题后面写子集、组合、N 皇后时就不会被这种隐藏 bug 反复卡住。2.5 运行验证与复杂度在本地调试时可以写一个简单入口if __name__ __main__: solution Solution() result solution.permute([1, 2, 3]) print(result)输出为[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]时间复杂度方面全排列共有n!个叶子节点每个叶子节点生成时又需要拷贝一次长度为n的路径所以整体复杂度可以记为O(n * n!)。空间复杂度主要由递归栈、path和结果数组构成属于这类搜索题型常见的代价。如果数组里有重复元素LeetCode 47 要求结果去重处理的思路是先排序然后在同一层递归中跳过“和前一个元素相同且前一个元素未被使用”的情况。建议先看懂 46再去做 47。3. LeetCode 55 跳跃游戏贪心为什么能省掉回溯3.1 题目理解与暴力搜索形态LeetCode 55 跳跃游戏的输入是一个非负整数数组nums。你初始位于数组的第一个下标每个元素代表在该位置可以跳跃的最大长度。只要求你判断能否到达最后一个下标。输入nums [2,3,1,1,4] 输出true从0出发元素值是2所以可以跳 1 步到下标1也可以跳 2 步到下标2但目标是最后一个下标4需要继续向后跳。如果对这题没有感觉可以先写出“回溯式枚举”的思路从当前下标出发枚举所有可以跳到的下一位置一直搜到终点。from functools import lru_cache from typing import List class Solution: def canJump(self, nums: List[int]) - bool: n len(nums) lru_cache(None) def dfs(pos: int) - bool: if pos n - 1: return True max_step nums[pos] # 从最大的跳跃长度开始尝试 for step in range(max_step, 0, -1): if dfs(pos step): return True return False return dfs(0)这段代码能表达决策树的搜索过程但它并不是实用的最终解法。原因是很多位置会从不同路径反复到达即使加了记忆化仍然可能在一个位置循环尝试一次可跳到的很多后续位置最坏情况下复杂度很高。3.2 决策树上真正关心的是“可达区间”回到决策树看看这题到底在搜索什么。从下标0出发任何能到达的位置都位于一个连续区间内而不是零散分布的点。更准确地说如果已经知道某个时刻能到达的最远位置是reach那么[0, reach]中的所有下标都是可达的。因为每一跳可以跳任意整数长度只要不超过nums[i]就不存在“中间某个位置跳不过去”的情况。一旦发现这个单调性就不用真的去遍历每一个跳跃分支了。每一步只需要做一件事用当前下标和当前元素值更新可达右边界。3.3 贪心代码每走一步都扩展最远边界from typing import List class Solution: def canJump(self, nums: List[int]) - bool: reach 0 n len(nums) for i in range(n): # 如果当前位置已经不可达说明前面存在断点 if i reach: return False # 更新最远可达边界 reach max(reach, i nums[i]) # 已经能到达最后一个位置可以提前结束 if reach n - 1: return True return True这个写法很短它把每一步都看作“维护一个可达区间”。区间右端点从 0 开始每次遍历到一个下标i都会尝试把右端点延伸到i nums[i]。如果遍历过程中发现某个下标i已经大于当前区间右端点那么说明中间出现了不可跨越的空白直接返回False。3.4 贪心正确性的简单论证代码短不代表不需要解释。LeetCode 55 能使用贪心的关键证明是下标i可达时从0到i的所有下标都已经可达。对任意可达下标i能到达的最远位置是i nums[i]。所以当前所有可达位置的并集是一个连续区间[0, reach]。只要仍然有未访问且可达的位置区间右端点就不会变小。当区间右端点覆盖n - 1时终点必然可达。反过来看如果某个位置不可达那么所有比它更靠后的位置也不可能通过“跳步”到达。因此循环中i reach就是失败的唯一判据。这也解释了为什么这里不需要回溯不是“运气好”而是问题的可达区间天然具有单调性贪心每一步选出的分支等价于搜索所有分支后的最大覆盖范围。3.5 和回溯的复杂度对比方法核心思想最坏情况下复杂度适用性回溯式枚举枚举每一步跳到哪里状态多且转移多可能超时无法判断是否可达时只适合小规模用例贪心每一步维护可达区间右端点O(n)只遍历一次数组LeetCode 55 标准解法LeetCode 55 的nums长度可以达到很大如果使用完整回溯输入稍微构造得“分支很多”就会超时。贪心解法只需要一次遍历连额外数组都不用开空间复杂度是O(1)。这道题还有个很自然的进阶版本 LeetCode 45要求求出跳到最后一个位置的最少步数。它同样可以用贪心但需要额外维护“当前这一步的覆盖终点”和“下一步能覆盖到的最远位置”本质是从“可到达哪里”变成了“每一步如何选择下一个落脚点才能让下一步覆盖更远”感兴趣的读者可以在做完 55 之后继续练 45。4. 局部最优的陷阱LeetCode 322 零钱兑换4.1 一个看似合理的贪心策略LeetCode 322 的问题是给定不同面额的硬币和一个总金额写出一个函数来计算可以凑成总金额所需的最少硬币个数。如果没有任何一种硬币组合能组成总金额返回-1。看到“最少”两个字第一反应很容易是贪心先把硬币面额从大到小排序。每次都用当前能用的最大面额去凑。剩余金额继续用下一面额。from typing import List def coin_change_greedy(coins: List[int], amount: int) - int: coins.sort(reverseTrue) count 0 for c in coins: count amount // c amount % c return count if amount 0 else -1这个代码看起来完全符合直觉面额越大单枚硬币覆盖的金额越多应当能减少硬币数量。4.2 一个让贪心失败的反例看这个输入coins [1, 4, 5] amount 8贪心策略会这样算取面额 5剩余 3硬币数 1 取面额 1剩余 2硬币数 2 取面额 1剩余 1硬币数 3 取面额 1剩余 0硬币数 4最终答案是4枚硬币5 1 1 1。但最优解其实是4 4只需要2枚硬币。问题出在哪里决策树的每一层都在选“当前金额下最大面额”但这会让后续金额变成一个“很难拼”的数字。更大的面额虽然减少了当前这一步的数量却堵死了后续组合出更优结构的可能性。局部最优不等于全局最优。4.3 这类问题更适合动态规划LeetCode 322 中硬币数量是无限的因此可以按“金额”从小到大计算最少硬币数。from typing import List class Solution: def coinChange(self, coins: List[int], amount: int) - int: dp [amount 1] * (amount 1) dp[0] 0 for current in range(1, amount 1): for coin in coins: if current - coin 0: dp[current] min(dp[current], dp[current - coin] 1) return dp[amount] if dp[amount] amount else -1对coins [1, 4, 5]amount 8时dp[4] 1代表用 1 枚 4 元硬币凑到 4 dp[8] min(dp[8], dp[4] 1) 2代表用两枚 4 元硬币凑到 8最后返回dp[8] 2。动态规划之所以能解决这里贪心解决不了的问题是因为它不会只保留一条分支而是把所有子金额的最优解都保存下来在完整解空间里找全局最小。值得注意的是这个示例只是用来解释“贪心可能错”的LeetCode 322 本身的标准解法是动态规划不能把上面的贪心代码作为题解提交。4.4 什么时候敢用贪心两条性质一道最值题不能用“感觉”判断能不能贪心而应该从两个角度检查贪心选择性质每一步做出的局部最优选择是否一定包含在某个全局最优解中。最优子结构问题的最优解是否包含子问题的最优解。LeetCode 55 跳跃游戏满足这两点因为可达区间的扩展是单调的从当前可达集合中选“最远点”不会破坏后续判断。LeetCode 322 的普通零钱兑换不满足第一点因为局部选最大面额可能破坏后续最优结构。如果无法严格证明又觉得搜索树太大可以退而求其次使用动态规划或记忆化搜索来保证正确性。对小白来说先把三类方法边界弄清楚比强行套贪心重要得多。5. 拿到题目后按什么顺序判断“回溯还是贪心”5.1 先回答三个问题很多刷题者拿到题就直接开始写代码其实还缺一道判断。每次看到题目先问自己三个问题题目要的是所有解、任意一个可行解还是全局最优解如果我要把所有可能选择画成树树的规模大约有多大每做一次局部最优选择是否有可能让后面的状态变差这三个问题的答案能很快帮你排除错误方法。5.2 回溯题和贪心题的表观差异题目特征大概率方向反例或风险要求返回所有排列、组合、子集回溯不撤销状态会漏解或重复只问是否能达到目标贪心或动态规划贪心需要证明否则可能错求最少/最大值且硬币单位不特殊动态规划贪心对非标准币值可能失效区间重叠、活动选择、种植鲜花贪心排序规则要选对否则结果不稳定解空间很大且只需要一个可行解回溯加剪枝或贪心 证明剪枝条件不充分仍会超时5.3 几个容易判断错误的场景有些题目看起来像贪心其实背后需要更复杂的维护。反悔贪心就是常见扩展方向。例如经典的任务调度问题先按收益从小到大排序用一个小顶堆维护当前已选任务当任务放置冲突或收益更优时把收益更低的弹出。这种策略仍然叫贪心但它在“必要的时候推翻了之前的局部最优选择”。LeetCode 中也有类似场景。遇到“最多/最少”且决策会互相影响的问题不要急着提交第一版贪心可以先用小规模数据和多组测试用例验证。6. 小白刷题最容易踩的坑和排查方法6.1 回溯结果重复或为空现象输出结果里所有路径都相同。某些排列缺失或出现重复。程序陷入死循环。可能原因把path直接加入结果没有拷贝。忘记在递归返回后撤销used[i]或path.pop()。递归终止后没有return导致继续执行循环。排列和组合问题混淆该用used却用了start。排查方式在进入递归前后打印当前状态print(before:, path, used) dfs() print(after:, path, used)如果进入前和返回后的状态不一样说明撤销步骤缺失。恢复状态后输出应完全一致。6.2 贪心用例一多就错现象本地测试几个例子都通过。提交时在一个看似普通的数据上失败。失败点通常发生在“最值之间产生冲突”的时候。可能原因排序规则不对。每一步只看当前收益忽略后面约束。没有证明只凭直觉。排查方式先把贪心结果和暴力结果做对拍。对自己实现的贪心函数同时写一个只处理小范围数据的枚举函数随机生成输入并逐项对比。# 伪代码对拍小数据 for nums in generate_test_cases(): a greedy(nums) b brute_force(nums) if a ! b: print(反例:, nums, a, b) breakLeetCode 无法直接进行随机对拍但你可以在本地生成多个简单用例再把这些用例复制到题解中验证。6.3 超时之后才想起剪枝现象回溯解法写在本地小样本上运行正常。提交后提示时间超出限制。可能原因决策树规模太大。没有利用排序、去重、上下界等条件剪枝。递归中重复创建了太多临时列表导致开销过大。处理思路先确认数据规模如果 n 达到 20 以上全排列型回溯基本都会超时。想办法剪枝组合总和类题目先排序如果当前选择已经超过目标值后面更大元素可以直接跳过。如果题目本质是求最值考虑能否换成动态规划或贪心。回溯的目的是用来把搜索过程看清不是所有题都能靠回溯 AC。6.4 排查顺序和自检清单遇到问题按此顺序排查顺序检查内容做法1数据规模和题目要求确认是全部解还是最优解2状态定义把 path、used、当前层数写在注释里3递归终止条件小规模用例手动走一遍4撤销操作对比递归前后状态5剪枝是否充分打印搜索次数估算复杂度6贪心策略是否有反例用暴力枚举做对拍7结果格式是否按要求排序或转为指定类型这个清单也可以当作发布前检查清单提交代码之前逐项看一遍能省下很多次无效提交。7. 别只背模板一组刻意练习顺序7.1 模板到底给了你什么回溯模板给的是“框架”不是“答案”。它能告诉你代码主要分终止条件、循环候选集、递归下一层、撤销状态。但这四部分放到不同题目中需要改的地方非常多全排列用used排除已用元素。子集用start避免选择前面已经处理过的元素。组合总和可以重复选同一个元素递归时传入的还是当前i。组合总和 II 需要先排序再在同层跳过重复值。括号生成则需要根据左右括号数量决定是否可以继续加括号。如果每道题都从同一套模板出发还要理解“为什么这里参数不一样”这样才算真正掌握回溯。7.2 回溯练习题目清单LeetCode题目核心练习点46全排列used 标记 状态撤销78子集start 控制选择起点77组合start 的另一种应用39组合总和同一元素可重复选择40组合总和 II排序后同层去重22括号生成根据左右括号数量剪枝17电话号码的字母组合多组候选集合131分割回文串在字符串上做决策我建议按这个顺序刷前十道题不用追求速度而是把每棵树的形状写出来。例如组合总和题在纸上画出target7的搜索过程你才能理解为什么i不需要加一以及什么情况下可以提前break。7.3 贪心练习题目清单LeetCode题目核心练习点55跳跃游戏可达区间扩展45跳跃游戏 II每一步选择下一跳能覆盖最远的位置122买卖股票的最佳时机 II局部利润叠加455分发饼干排序 双指针860柠檬水找零面额取舍435无重叠区间按右端点排序452用最少数量的箭引爆气球区间合并与贪心证明刷贪心题时不要只看代码要问自己两个问题为什么按右端点排序为什么当前选择的区间不会让后续更差如果能用一个反例推翻策略说明还没证明到位。7.4 每道题复盘时至少问自己四件事做完一道题尤其是 AC 之后至少再花一点时间复盘如果这是一棵决策树哪些分支是可以剪掉的我的解法是在遍历整棵树还是只走了一条路径如果改成贪心需要证明什么能不能举出反例如果题目数据范围扩大十倍当前代码还能不能过真正提升刷题效率的从来不是题量而是每次把“为什么这样写、为什么不用另一种写法”想清楚。把 LeetCode 46、55、322 这三道题放到一起对比你就能看到回溯、贪心、动态规划在同一类问题上的取舍回溯帮你看清完整决策树贪心帮你在可证明的场景下节省搜索而动态规划用空间换时间解决局部最优不成立的最值问题。建议新手不要一上来就跳进难题。先用[1,2,3]这种最小用例画出决策树然后在代码里加入剪枝、打印状态、对比不同策略直到你可以清楚地解释每一步为什么不用回头。这种训练方式比把几十份题解代码背进收藏夹更有用。