回溯还是贪心？用决策树看懂算法题的选择逻辑

算法题刷到一定阶段很多人都会进入一个奇怪的瓶颈回溯模板背得滚瓜烂熟贪心口诀也抄了好几页但拿到新题还是不知道用哪个。这往往不是因为题目刷得少而是因为没理解两种算法背后的决策逻辑——回溯的本质是穷举它在构建一棵决策树贪心的本质是“选当前看起来最好的一步”它在走一条局部最优的下坡路。如果能把这两件事放到同一张图里想很多题会突然变得清晰。这篇文章是“小白怎么刷 LeetCode”系列的第 8 篇我打算从决策树的角度把回溯和贪心放在一起串讲。不仅讲框架还会用 LeetCode 原题演示什么时候该用回溯去搜所有解什么时候该用贪心去找最快解以及为什么有的题贪心能被证明是对的有的题贪心却会翻车。1. 从一道“看似简单”的题说起为什么背模板会失灵先别急着看定义我们看一道很经典的入门题LeetCode 455「分发饼干」。假设你有一群孩子每个孩子的胃口是g[i]你有一堆饼干每块饼干的大小是s[j]。一块饼干只能喂一个孩子而且只有饼干大小不小于孩子胃口时孩子才能吃饱。问最多能满足多少个孩子。很多同学第一反应是这不就排序吗小饼干喂胃口小的孩子思路对这就是贪心。但如果我再换个问法请把所有能让孩子吃饱的分配方案都列出来。这时你会发现“排序后从前往后喂”已经不够了你需要枚举每个孩子吃哪块饼干、每块饼干给哪个孩子。这个“把所有方案都列出来”的需求恰恰是回溯的典型场景。同一个数据场景因为问题问法不同解法从贪心变成回溯。这就是为什么只看结论、不深究问题结构的刷题方式很难持久。回溯和贪心不是互斥的两套模板而是对应两种不同的“做选择”方式维度回溯贪心核心逻辑穷举所有决策分支每步只选当前最优目标找所有解/判断是否存在解找一个最优可行解空间复杂度通常 O(深度) 递归栈通常 O(1) 或 O(n) 辅助时间复杂度往往是指数级往往线性或 O(n log n)适用条件几乎通用但可能超时必须有“局部最优能推全局最优”的性质你可以把“能不能背模板”这个问题放一边先问自己两个问题这道题是让我穷举“所有可能”还是只让我找一个“最优答案”如果每一步选择都会影响后面的结果我需不需要“反悔”去尝试另一条路想清楚这两点你就知道决策树才是贯穿回溯和贪心的底层工具。2. 回溯算法把递归过程画成一棵决策树2.1 回溯到底在做什么回溯算法常常和深度优先搜索DFS、递归放在一起讲。严格来说DFS 是一种遍历方式回溯则是在 DFS 的过程中加入了状态重置也就是“反悔”操作。通俗地说回溯就是一条路走到黑发现走不通或已经收集到目标结果时退回上一个岔路口换另一条路继续走。这个“退回”的动作在代码里经常表现为path.append(choice) # 做出选择进入下一个状态 dfs(...) # 递归处理后续步骤 path.pop() # 撤销选择回到岔路口如果你用决策树来表示整个回溯过程就是对这棵树的先序遍历树的每一层代表“当前正在处理第几个位置”。每个节点往下扩展出的分支代表“当前位置可以选哪些值”。根节点到叶子节点的一条路径往往就是一个完整的候选解。很多文章会把下面的代码称为“回溯模板”result [] def backtrack(路径, 选择列表): if 满足结束条件: result.append(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择模板没有错但它只是骨架。真正难的是你要能画出这道题自己的决策树。如果画不出树模板就是死记硬背。2.2 从“选或不选”理解决策树LeetCode 78 子集LeetCode 78「子集」是理解回溯决策树的最佳入门题之一。题目要求给定一个不重复元素的整数数组nums返回所有可能的子集。对于每个元素nums[i]决策只有两种选它还是不选它。所以决策树是一棵二叉树处理 nums[0] / \ 不选 选 / \ / \ 不选 nums[1] 选 nums[1] 不选 nums[1] 选 nums[1]按照这个树写代码可以有两种写法。第一种写法是“对每个元素选/不选”的 DFSdef subsets(nums): res [] path [] def dfs(i): # 已经处理完 nums 中所有元素path 是一个子集 if i len(nums): res.append(path[:]) return # 1. 不选 nums[i] dfs(i 1) # 2. 选 nums[i] path.append(nums[i]) dfs(i 1) path.pop() dfs(0) return res第二种写法更常见它把决策树理解为“当前从哪个下标开始选”def subsets(nums): res [] path [] def dfs(start): # 进入该节点时path 已经是一个合法子集 res.append(path[:]) for i in range(start, len(nums)): path.append(nums[i]) # 选择 nums[i] dfs(i 1) # 下一个元素只能从 i1 开始选避免重复 path.pop() # 撤销选择准备选下一个元素 dfs(0) return resnums [1, 2, 3]时第二种写法的输出是[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]注意res.append(path[:])。很多新手刚开始会写成res.append(path)最后发现返回的全是空列表。原因是path是同一个列表对象回溯过程中一直在变append(path)只是把引用放进了结果数组后面path.pop()会把这个引用指向的列表改掉。使用path[:]相当于复制一份当前状态的快照。看子集题的核心并不是背住上面的模板而是理解递归每进入一层就相当于向决策树深处走一步for循环负责横向遍历当前层的所有选择递归调用负责向下一层深入pop负责回到当前层、尝试另一个分支。2.3 排列类题目如何画决策树子集问题关注的是“选哪几个元素”排列问题关注的是“元素按什么顺序排列”。所以排列问题的决策树和子集不同每一层选择的是“当前位放哪个元素”。已经被放在前面位置的元素后面不能再选。以 LeetCode 46「全排列」为例画出决策树前两层大致是这样[] / | \ [1] [2] [3] / \ / \ / \ [1,2] [1,3] ...对于每个位置可选择的列表是“所有还没使用过的元素”。因此我们需要一个used数组来记录哪些元素已经在路径里。def permute(nums): res [] path [] used [False] * len(nums) def backtrack(): # 所有元素都已经放进路径得到一个排列 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]) backtrack() # 撤销尝试下一个可用元素 path.pop() used[i] False backtrack() return res子集和全排列的代码结构非常像但决策树不同。如果你只记住了“模板”却没理解“哪些元素可以作为当前层的分支”就会出现在排列代码里用start、在组合代码里漏掉used之类的错误。2.4 剪枝并不是所有分支都要走到叶子回溯最大的痛点是指数级的时间复杂度。以 n 个元素的全排列为例如果不做任何优化有 n! 种叶子状态。因此很多优化的核心思路是剪枝即在递归过程中提前判断某些分支不可能产生合法解直接跳过。举个例子LeetCode 40「组合总和 II」要求每个数字在每个组合中只能使用一次并且结果集不能包含重复组合。一种经典做法是先对candidates排序然后在 for 循环里做同一层去重def combinationSum2(candidates, target): candidates.sort() res [] path [] def dfs(start, remain): if remain 0: res.append(path[:]) 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]) dfs(i 1, remain - candidates[i]) path.pop() dfs(0, target) return res这里的关键点在于if i start才是“同一层去重”。如果写成if i 0 and nums[i] nums[i-1]: continue会错误地把不同层之间的重复值也跳过很可能导致漏解。你不需要一开始就把所有剪枝技巧都背下来但心里要有这根弦回溯的代码行数越少不代表效率越高真正有效率的回溯往往是递归层数可控、剪枝逻辑清晰的状态穷举。3. 贪心算法为什么“局部最优”能够通向“全局最优”3.1 贪心的直觉如果说回溯是“把所有路都走一遍再挑答案”贪心就是“每一步都走当前看得最顺眼的路并且永远不回头”。以分发饼干为例。既然每块饼干只能喂一个孩子那么想让“喂饱的孩子数量”最大最自然的想法是把尽量小的饼干喂给胃口尽量小的孩子这样大饼干可以留给后面的孩子。排序 双指针就能实现def findContentChildren(g, s): g.sort() s.sort() child 0 cookie 0 while child len(g) and cookie len(s): if s[cookie] g[child]: child 1 # 无论能否满足这块饼干都已经消耗掉 cookie 1 return child这段代码不需要递归不需要回溯撤销。每次只看当前最小的饼干能不能满足当前最小的孩子能满足就喂不能满足就丢掉这块饼干。整个过程没有“反悔”因为我们已经通过排序保证了“当前的局部选择不会牺牲全局最优”。3.2 什么时候贪心才成立两个关键性质很多文章会提到两个术语贪心选择性质每一步的局部最优选择最终能组合成全局最优解。最优子结构一个问题的最优解包含其子问题的最优解。大白话就是你要能证明我这一步选择不会把后面的路堵死。如果某一步塞给小饼干一个胃口大的孩子导致胃口小的孩子没饼干吃那贪心就失效了。LeetCode 455 之所以能用贪心是因为“喂饱更多孩子”不要求给某个孩子指定哪块饼干只关心数量。小饼干若不能满足当前最小胃口那它也满足不了任何胃口更大的孩子留之无用这就是丢掉的依据。面试中如果让你证明贪心算法常见的三个思路交换论证假设一个最优解里当前这一步没按贪心策略来。证明可以通过交换两个元素把它调整成按贪心策略的解结果不会变差。归纳法证明贪心做完第一步后剩余问题仍然是同构的子问题并且可以用同样的策略继续。反证法假设贪心解不是最优导出矛盾。LeetCode 55「跳跃游戏」是另一个特别好的例子。题目给定一个非负整数数组nums[i]表示你在下标 i 处最多能往前跳的步数问能否到达最后一个下标。很多人的第一反应是用递归穷举跳法。但你如果画出决策树会发现树上有大量重叠子问题“跳到位置 3”可能是从位置 0 跳两步来的也可能是从位置 1 跳两步来的而之后的分支完全相同。更漂亮的是贪心思路我们不关心具体每一步跳到哪里只维护一个变量farthest表示“目前能到达的最远位置”。遍历数组时一旦发现当前位置已经大于farthest说明前面的所有跳法都到不了这里直接返回 False否则用当前能跳的最远距离更新farthest。def canJump(nums): farthest 0 n len(nums) for i in range(n): if i farthest: return False farthest max(farthest, i nums[i]) if farthest n - 1: return True return True这个解法为什么正确因为从位置 i 能跳到的最远位置是i nums[i]而它覆盖了 i 到i nums[i]之间的所有位置。我们只要保证最远可达位置不断前进就不需要真的在每一层分叉去考虑“跳 1 步还是跳 2 步”。换句话说贪心把决策树里的很多等价路径合并成了一条“最远前沿”。3.3 一个反例贪心不是“看起来合理就行”只讲贪心正确的例子会让新手误以为贪心是一个靠猜就能用的算法。实际上需要反例来提醒自己。LeetCode 322「零钱兑换」给定不同面额的硬币 coins 和一个总金额 amount求凑成总金额所需的最少硬币个数。直觉上可能会想每次尽量用大面额硬币零钱数量不就少了吗对于硬币[1, 3, 4]、amount 6贪心会先拿4再用两个1一共 3 枚但最优解是3 3只需要 2 枚。问题出在哪里用一个 4 元硬币后剩余金额 2 只能由 1 元硬币补足这些 1 元硬币的数量把前面的“大额优势”抵消了。因为这个问题的后续选择依赖之前选择过的硬币面额简单的“当前最大面额优先”并不能保证全局硬币数最少。这类题正确的方向通常是动态规划或带剪枝的搜索而贪心就只能歇菜。所以遇到“看起来可以用贪心”的题先别急着写sort 循环先构造几个小用例验证一下尤其是考虑反例有没有可能你这一步选的局部最优导致后面的代价异常高4. 回溯和贪心怎么选三个实战判断信号刷题多了你会发现题目往往不会直接告诉你“本题请用回溯”或“本题请用贪心”。你需要从题干中提取问题模式。4.1 先看问题问的是什么我通常用下面几个信号做初判出现“返回所有组合 / 全排列 / 所有可能路径 / 所有子集”等字眼基本是回溯。因为这类问题要求穷举所有结果贪心只能提供一个答案。出现“最大 / 最小 / 最多 / 最少 / 是否可行”需要继续分析是否具备贪心性质。如果当前选择不影响后续选择贪心通常值得尝试如果不确定先用回溯或动态规划保证正确性再考虑优化。出现“共有多少种方案数”这类计数问题很多也能用回溯剪枝不过最优往往是动态规划。如果数据范围很小回溯完全够用。需要对一组元素排序后再做选择的比如会议安排、饼干分配、区间重叠这类题往往和贪心有关。4.2 看是否存在“后悔”的需求如果你模拟一下手工决策过程发现自己需要在走完一组方案后回到上一步重新尝试另一种方案那么这是回溯。如果你发现每一步都有一个“显然不差”的选择并且不需要记录之前是怎么选的那么这是贪心。LeetCode 79「单词搜索」是一个很好的例子。在二维网格中找单词当你匹配到某个字符后下一步有多个方向可选。如果沿着一个方向走到底发现不匹配需要退回上一个格子尝试另一个方向。这个“退回”动作让题目必须使用回溯 方向偏移数组而不是贪心。4.3 关注数据范围面试和竞赛中数据范围是重要的提示如果 n 很小例如 n 15 或 20很可能是在暗示可以枚举所有状态子集回溯或状态压缩都是合理的。如果 n 很大比如 10^5 甚至更大回溯几乎一定会超时。这时应优先考虑贪心、排序 扫描、双指针或动态规划。不过要记住数据范围只是辅助判断不是绝对规则。有些人拿到n 20的题也非要用贪心反而错过回溯的常规解法有些人遇到n 10^5却强行写 DFS显然也不合理。5. 一道题的两种视角用“目标和”看懂穷举与局部最优LeetCode 494「目标和」在热搜里经常出现。我们用它来看“回溯怎样把问题变成决策树”。题目给你一个整数数组 nums 和一个整数 target。你可以给每个元素前面添加或-然后串联起所有整数问能构造出多少种表达式使得运算结果等于 target。每个数字前有两种符号所以决策树是一棵二叉树0 2 -2 1 -1 1 -1 ... ... ... ...如果数据量不大直接从第一个数开始枚举写一个回溯def findTargetSumWays(nums, target): n len(nums) count 0 def dfs(idx, current_sum): nonlocal count if idx n: if current_sum target: count 1 return # 分支一当前数字前加 dfs(idx 1, current_sum nums[idx]) # 分支二当前数字前加 - dfs(idx 1, current_sum - nums[idx]) dfs(0, 0) return count这个版本就是一棵递归二叉树叶子数量为 2^n。LeetCode 上如果 n 较大会超时。所以要引入记忆化搜索把(idx, current_sum)这个状态对应的结果缓存起来避免重复计算这就是动态规划的雏形。而如果用贪心做这道题你会发现很不自然到底当前数字前面加正号还是负号取决于后面数字怎么凑单个局部选择很难证明全局最优。因此像“目标和”这类问题通常不是贪心的主战场。把回溯、贪心、动态规划放在一起比较会得到一张有意思的图回溯从根节点出发遍历所有路线收集目标叶子。贪心从根节点出发每一步只看一个“当前最优”孩子一路走到底不看其他分支。动态规划把决策树的每个节点状态缓存下来让重复节点只计算一次。所以如果你已经会画决策树那么学动态规划时也会轻松一些因为动态规划本身就是“有重叠子问题的 DAG 最短路径计算”只不过它通常用递推而不是递归实现。6. LeetCode 实战推演从回溯超时到贪心通过下面我们完整走一遍解题流程题目还是用 LeetCode 55「跳跃游戏」的变体思考题不仅要判断能否到终点还要输出到达终点需要的最少跳跃次数。这是 LeetCode 45「跳跃游戏 II」。先说明思路最直接的想法是用 DFS。从位置 i 出发最多可以跳[1, nums[i]]步所以需要模拟每一种跳法记录跳到终点的最小步数。这个思路对应一棵很宽的决策树如果不加优化当数组长度超过一定规模后会超时。为了在文章中清楚展示回溯结构先用递归思想写出伪代码式版本def jump_backtrack(nums): n len(nums) min_steps float(inf) def dfs(i, steps): nonlocal min_steps if i n - 1: min_steps min(min_steps, steps) return # 如果当前步数已经不可能比历史最优更小剪枝 if steps min_steps: return max_step nums[i] # 从远到近尝试通常更容易先找到可行解 for step in range(max_step, 0, -1): dfs(i step, steps 1) dfs(0, 0) return min_steps这段代码能通过小规模用例但在 n 很长的情况下会出现大量重复搜索同一个位置可能从不同前驱节点到达多次而每一次都要重新扩展它的所有后继分支。为了让它不过于难看我甚至加入了“如果当前步数已经超过已知最优解就剪枝”的逻辑但这个剪枝仍不能根治指数级的坏情况。这就是典型的“回溯能做但不够高效”。当你发现决策树中存在大量重复子树时就要停下来思考更好的算法。本题的标准解法是贪心维护三个变量farthest当前一步跳跃能够到达的最远位置。current_end当前这一步跳跃的右边界当遍历到它时说明必须再跳一次。steps已经跳跃的次数。遍历数组时每次都更新farthest当i到达current_end说明上一跳覆盖的区域已经走完还没有到终点因此必须开启新的一跳def jump(nums): n len(nums) steps 0 current_end 0 farthest 0 for i in range(n - 1): farthest max(farthest, i nums[i]) if i current_end: steps 1 current_end farthest if current_end n - 1: break return steps这个解法的时间复杂度是 O(n)空间复杂度 O(1)。它巧妙的地方在于完全不需要在“具体跳到哪里”上做选择只用维护一个最远边界。走到当前边界再被迫跳一次这样就保证了“能在最少的跳跃次数内把可达范围扩展得最大”。这就是从回溯到贪心的优化思维先用决策树想清楚可能的决策有哪些再试图在树里找一条不需要回溯所有分支的捷径。若捷径已经被证明成立贪心就是最优解。7. 回溯 贪心常见错误与调试清单作为初学阶段你大概率会遇到下面这些坑。我把它们集中列出来方便你写代码时对照检查。问题现象常见原因解决思路返回结果全是空列表res.append(path)直接追加引用而 path 在回溯中被修改改成path[:]或list(path)复制组合/子集结果出现重复未对同层重复元素去重或使用了错误的位置索引判断先排序再通过i start判断同层重复并跳过全排列缺少元素选了某个元素后没有在递归前标记used[i] True或者没有恢复检查used数组的标记和撤销是否成对出现字符串/数组越界递归进入下一层时没有检查边界或 for 循环范围边界不对打印当前参数确认状态是否向终止条件收敛贪心提交后发现某些用例失败忽略了反例局部最优未必能推出全局最优先用小规模暴力解验证再对比贪心结果使用贪心前没有排序贪心往往需要先排序或构造一种有序的扫描顺序确认是否需要对输入排序或改用优先队列维护“当前最优”数组排完序后直接改变原数组导致问题无法回溯排序破坏了元素在原数组中的位置关系如果题目依赖原始下标用(value, index)结构存储后再排序除了表格里的问题我还建议你养成一套固定的调试流程用小数据把决策树画出来手动模拟一遍。在递归函数入口打印当前path、可选列表和递归深度。检查每次递归是否都会向“更接近终止条件”的方向前进防止死循环。检查恢复现场时所有在递归前修改的状态是否都已恢复。回溯题的调试尤其依赖“状态恢复”。如果忘记pop()后面的分支会带着上一次选择的结果继续走导致输出大量错误解。8. 总结与下一步行动建议从决策树的角度看回溯和贪心其实是“同一张图上的两种走法”回溯愿意遍历每一个岔路口贪心则希望每一步都能一眼看出哪个岔路口最值得走。回溯更通用、更稳健缺点是慢贪心更快速、更精妙但只有在满足“贪心选择性质”的基础上才能成立。我建议你在接下来一周内做三件事用这四道题巩固回溯LeetCode 78 子集、46 全排列、40 组合总和 II、79 单词搜索。每道题不要先看题解先自己画决策树再对照代码。用这三道题练习贪心的证明思维LeetCode 455 分发饼干、55 跳跃游戏、45 跳跃游戏 II。尝试用交换论证说明为什么局部最优成立。找一个失败案例来“打脸”贪心比如 LeetCode 322 零钱兑换。自己构造一个硬币组合证明“每次选最大面额”并不一定最优再回头理解为什么零钱兑换需要动态规划而不是字典序。下一步还可以继续学习“回溯的剪枝艺术”和“带备忘的回溯如何自然过渡到动态规划”。当你看到一道求方案数的题能从 2^n 暴力搜索写成f(i, target)的记忆化搜索再写成自底向下的 DP你对算法题的理解就真正上了一个台阶。如果这篇文章对你有帮助可以顺手收藏备用。也欢迎在评论区聊聊你最近卡住的一道题大家一起拆解它的决策树。