回溯与贪心：从决策树视角理解搜索与最优选择

如果你在 LeetCode 上刷到“组合总和”“全排列”“目标和”这一类题很难不遇到一个词回溯。再往后翻题解又会撞见另一个词贪心。很多人会告诉你回溯就背模板贪心就靠感觉。结果就是模板背得越熟遇到新题越心虚感觉来得越快WA 得也越稳。今天这篇想换个角度讲回溯和贪心本质上都在同一棵“决策树”上做搜索。差别不是“一个要用 for 循环”或“一个要用 while 循环”而是“搜完整棵树再回退”和“只沿着一条局部最优路径往下走不回头”的区别。把这个底层视角建立起来很多刷题时的死记硬背都可以丢掉。1. 为什么你把回溯背得滚瓜烂熟换个题还是不会1.1 从“背模板但不会变通”说起见过不少刚开始刷题的朋友第一道回溯题是“全排列”把模板抄了三遍AC 之后觉得自己会了。结果第二道题换成“子集”第三道换成“组合总和 II”马上出问题不知道该在哪个位置加if不知道该往 DFS 里传什么参数path.pop()放错位置导致答案变成空集合。这不是笨也不是刷题量不够。真正的原因是一上来就背“终止条件 for 循环 递归 撤销选择”这个外壳却不知道这个外壳到底在模拟什么。如果我们把记忆起点换一下局面会完全不同。1.2 背后真正能统一的底层模型决策树几乎所有回溯题都可以画成一棵树。所谓“回溯”就是在这棵树上做深度优先遍历走到底就记录没路走就退回上一个岔路口换一条分支继续走。举一个最经典的例子给定数组[1, 2, 3]请输出所有子集。这个问题可以这样看对每个数字决策是“选它”或者“不选它”。先对 1 做决策产生两个分支每个分支里再对 2 做决策最后对 3 做决策。整棵树的叶子节点就是所有子集。“全排列”也是类似。第一层确定第一个位置放谁有三个选择第二层确定第二个位置放谁在上一步剩余元素里选直到所有位置都被填满。一旦你看懂了这棵树回溯代码写出来只是顺带的递归函数负责“走到下一层”for 循环负责“这一层有哪些岔路”撤销选择负责“从一条岔路退回来再走另一条岔路”。模板不是不重要而是它只是这棵树的遍历代码。真正决定一道题难度的不是遍历代码而是树长什么样每个节点有哪些选择走到哪里算一个答案哪些分支根本不用走。1.3 这也解释了为什么贪心题“看起来没有模板”因为贪心不走完整棵树。它没有“退回上一站重新选”的动作也不打算把整棵树的叶子看完而是每一步只按某个标准挑一个分支往下钻。所以贪心不需要一个统一的模板它需要的是一个“每一步都选得很好”的决策规则。这不是说贪心比回溯简单。事实上贪心的难点从“怎么写”变成了“为什么这个局部选择最后不会让你后悔”。如果证明不了这一点所谓的贪心只是猜。2. 先画一棵决策树把回溯和贪心放在同一张图里看2.1 所有“选择类问题”都能变成树刷题时判断一道题能不能抽象成决策树标准很朴素求解过程是不是由一连串“选择”组成。比如“跳跃游戏”站在下标 0你能选择跳 0 步、1 步……直到nums[0]步这会决定你到达哪个位置到了新位置又有一组新选择。画成树就是多叉树。再比如“硬币找零”要找 6 块钱第一次可以选面额 1、3、4 中的任意一枚选完后剩下要找的钱变了下一层又有新的选择。画成树从根节点到叶子的路径就是一种找零方案。只要题目可以描述成“每次从若干选项里选一个选择会影响后续状态”它背后就存在一棵决策树。至于用什么算法解决本质上是问你要不要把这棵树走完把整棵树走完回溯、DFS走完但走到重复状态时利用历史答案记忆化搜索 / DP每一层只按局部标准挑一个孩子继续走贪心。2.2 回溯是“允许后悔”的深度优先遍历回溯和 DFS 的关系网上有很多争论。从刷题的角度我更愿意把回溯理解成“带状态还原的 DFS”。为什么需要状态还原因为在树上深度优先遍历时如果你不把当前层做过的选择撤销那么另一条兄弟分支看到的初始状态是被污染过的。比如全排列代码里常见的path.append(nums[i])递归完后必须path.pop()。不做这一步第一次递归返回后path里还留着上一个分支的尾巴后面继续 for 循环时下一次append的就不是想象中的新路径。所以回溯代码的骨架不是“三步走”而是一个循环过程def dfs(当前状态): if 到达叶子节点或满足结束条件: 记录当前状态对应的答案 return for 选择 in 当前层可选集合: 更新状态做选择 dfs(更新后的状态) 恢复状态撤销这一层产生的变化这个骨架要能工作前提是你知道“当前状态”是什么。很多题不是没法套模板而是把“状态”简化错了。2.3 贪心是“不回头”的启发式下钻同样的决策树贪心是怎么走的假设你在一个二叉树的根节点目标是找一条从根到叶子、使某个目标函数最大的路径。如果每一步只选当前能看到的子节点里目标值更大的那个一路走到底不做任何回退这种策略就是贪心。LeetCode 55 跳跃游戏可以很直观地体现这一点。题目大意是给定一个非负整数数组每个元素表示你在该位置最多能往后跳多远判断能不能跳到最后一个下标。解法之一是维护一个当前能到达的最远位置max_reach。遍历数组时不断更新它def canJump(nums): max_reach 0 for i in range(len(nums)): if i max_reach: return False max_reach max(max_reach, i nums[i]) return True从决策树的角度理解这段代码它没有去枚举“在这一步具体跳到哪里”而是不断放大“当前可达区间的最右边界”。站在任意位置i时只要i已经被覆盖到那么所有不超过max_reach的位置都可达。这个信息比“具体选哪个跳法”更重要因为它直接回答了可到达性的最大值。2.4 一张表看清两者的差异对比维度回溯贪心是否遍历完整决策树通常需要深度优先遍历很多分支只沿一条策略路径走下去是否能回退重选能通过撤销选择回退不能选完不回头适合求解的问题所有可行解、方案数、排列组合等局部最优能推出全局最优的问题复杂度特征通常指数级但可剪枝优化通常线性、排序后接近线性或 O(n log n)对状态的要求显式维护路径和相关状态维护对下一步决策有帮助的“当前最优指标”代码的通用性有相对统一的模板骨架每个题目的贪心策略都不一样这张表不是让读者背诵的。它可以作为一道新题到手后的定位工具如果题目要求“返回所有方案”大概率不是贪心如果题目要求“是否可行”或“找最优且能证明局部最优”才值得考虑贪心。3. 回溯题真正的分水岭不是模板而是剪枝和状态设计3.1 为什么“套模板”会失灵以 LeetCode 494 目标和为例。题目大致是给你一个非负整数数组和一个目标整数你可以在每个数前面放或-要求最后表达式结果等于目标值返回方法数。如果机械地套“全排列/组合”模板很容易把“状态”定义成“当前已经选择的正负号序列”然后判断整个序列和是否为 target。这样也可以做但代码会变得很绕而且很多剪枝加不上。其实这一题的决策树非常整齐每个数字做一次“加还是减”的二选一。真正的状态只需要两个值当前处理到第几个数i以及当前累加和cur_sum。递归终止条件不是“path 长度达到 n”而是i len(nums)。如果让我给初学阶段的学习者建议我会说先别急着套三行模板先把下面三件事写出来这一层的选择是什么选择之后下一层的状态怎么变化到达什么状态时可以停止并记录答案。3.2 从“必须记路径”到“只累加答案”很多回溯题其实不需要真正记录路径比如目标和要求的是方案数不是“加加减减”的完整表达式。既然只需要计数DFS 返回值或全局计数就够了没必要维护path。下面是一种很常见的回溯写法用于演示决策树的递归结构。为了让你看清楚树的形状这里不优化成 DPclass Solution: def findTargetSumWays(self, nums: List[int], target: int) - int: n len(nums) def dfs(i, cur_sum): if i n: return 1 if cur_sum target else 0 # 决策1当前数字前放 # 决策2当前数字前放 - return dfs(i 1, cur_sum nums[i]) dfs(i 1, cur_sum - nums[i]) return dfs(0, 0)这段代码在 LeetCode 上会超时因为它是真正的 2 的 n 次方指数遍历。但它非常适合用来理解“决策树”。有了这个版本后续你可以继续观察哪些子树会被重复访问去掉重复访问是不是就变成了记忆化搜索再继续压缩是不是就是动态规划回溯题的第一层价值就是让你能写出这个最朴素的搜索框架。在此基础上才谈得上优化。3.3 剪枝不是锦上添花是很多题的 AC 关键如果回溯题的数据范围稍微大一点不剪枝基本过不了。剪枝的本质是在决策树上找到那些“没必要走的分支”提前停掉。剪枝至少有两种常见来源约束剪枝当前部分解已经违反题目条件继续走一定不会成功。顺序剪枝提前排序让不可能成功的解更快暴露或者避免重复组合被反复枚举。拿“组合总和 III”举例要求只用 1 到 9 的数字选出 k 个数每个数字最多用一次使得它们的和正好为 n。朴素的递归可以写成从当前位置start往后选一个数加入路径然后递归。但如果当前已经选了几个数即使后面全选最小数字也无法达到 n或者当前和已经超过 n就可以提前返回。常见写法里的if target 0: return就是一种最简单也最有效的约束剪枝。再配合“从 start 开始枚举”天然避免了重复组合。更进阶一点很多组合类问题会先对候选数组排序然后在 for 循环里写for i in range(start, len(candidates)): if candidates[i] remaining: break ...因为数组有序当前元素已经大于剩余目标后面更大的元素更不可能满足要求所以直接 break。这是典型的顺序剪枝。很多人说回溯“暴力”但加好剪枝的暴力往往比没剪枝的暴力快几个数量级。3.4 状态还原是最容易被忽略的“隐形雷”还有一类报错不是超时而是答案出现“幽灵路径”。常见原因递归函数里用了同一个可变容器比如 Python 的path列表往下传的时候传的是引用。如果递归结束后不把刚加进去的元素弹出来下一轮 for 循环会在这个“被污染”的路径上继续添加。再比如下面这种写法dfs(path [nums[i]], i 1)它每次生成一个新列表天然不会污染兄弟分支。好处是代码简单坏处是每次递归都复制一次数组空间开销更大。对于深度不高的回溯题很多人也喜欢这么写因为它几乎不会出现状态还原遗漏的问题。如果使用“先 append递归再 pop”的写法则必须保证每一层递归返回后当前层状态和进入前完全一致。排查问题时可以重点检查这两类地方同一个path是否被多个分支共享递归中途 return 时是否遗漏了应该执行的撤销步骤。我见过很多“为什么结果重复”“为什么结果为空”的提问最后都出在这两处。这比不理解回溯思想更常见。4. 贪心不是“感觉对”它要求你证明局部最优能推出全局最优4.1 贪心策略“看起来对”但实际错不少同学对贪心的理解是每一步都取当前看起来最好的选择。这句话作为直觉没错但当“看起来最好”不能覆盖全局最优时贪心就错了。最典型的例子是硬币找零假设硬币面额有 1、3、4要凑出 6。如果采用“每次尽量选大面额”的贪心策略先选 4剩余 2再选 1再选 1一共 3 枚。但最优解是 3 3只要 2 枚。所以贪心算法必须回答一个问题为什么每一步的局部最优选择不会影响后续达成全局最优如果回答不了就只能把它当“启发式”使用在算法题里很容易被反例干掉。4.2 跳跃游戏里为什么贪心可以跳跃游戏的贪心为什么对因为它在维护的是“当前可达的最右边界”。你不需要关心具体跳到哪里只需要知道从当前已覆盖范围内的任意位置能不能把最右边界继续扩大。遍历到位置 i 时只要 i 本身在可达范围内更新max_reach max(max_reach, i nums[i])就不会漏掉任何可能。这个策略的“贪心”体现在每到一个位置都想把可达最右边界尽量推远。它之所以能得到全局可判断结果是因为“可达性”本身是单调的只要前面某个位置可达从它出发能覆盖到的最右位置是整个前缀里所有跳跃潜力的最大值。代码里不需要回退因为max_reach一直在累积之前所有位置可以带来的最远信息。与其说它是“局部最优”不如说它是在线性扫描中计算一个全局可达集合的边界。4.3 证明“局部最优就是全局最优”的两种常用思路不一定要写出严谨的数学证明才能做题但至少要有能力判断自己的策略方向是否合理。常见的证明套路有以下两种交换论证假设存在一个最优解当这个最优解与贪心选择不同时可以在不破坏可行性的前提下将最优解调整成包含贪心选择的解并且结果不差。于是贪心选择最终可以嵌入一个最优解。剪枝论证 / 替代论证证明任何一个可行解都可以被另一个“包含贪心选择”的可行解替代且结果更优或相等因此贪心选择的方案不会比最优解差。在学习阶段不需要把每个字写得很规范但应该养成“挑战自己”的习惯想出一个贪心策略后先尝试构造一个反例。构造不出反例再去写代码。如果每次都能快速构造反例说明这道题大概率不是贪心或者你的贪心方向不对。4.4 一个很实用的调试方法用暴力递归给贪心“对拍”和小白聊天时发现一个现象很多人不敢用暴力觉得暴力复杂度太高不能提交。但在做贪心题的时候暴力递归是最廉价的验证工具。你可以先用 DFS 写出“找所有方案并比较最优值”的朴素代码再把贪心代码和它同时提交到同一个输入样例上对比。数据量小的时候两者结果应该一致。一旦发现不一样立刻手动打出两个结果找出让你决策出错的那个样例。这个方法在面试准备和平时刷题中都很实用。贪心题的难处通常不是代码本身而是“你是怎么确定这个解法的”。暴力代码能帮你快速建立反例库时间久了你对贪心适用边界的嗅觉会比纯粹背题灵敏得多。5. 小白刷题的正确姿势先从“背模板”切换到“画决策树”5.1 拿到一道题至少先回答三个问题再写代码很多人打开编辑器就开始敲循环。其实最值得花时间的不是敲代码而是把题目翻译成决策树的结构。我更推荐按下面的顺序思考每一步要做什么选择做了这个选择后下一层面对的状态有什么变化什么时候这条路径可以停止是输出一个可行解还是只要求判断最优解“全排列”和“子集”之所以看起来难区分就是因为它们的树形不一样——一个是“排列所有剩余元素”一个是“每个元素选或不选”。“组合总和”又跟前两者不同因为它要求从有序候选数组中挑数并且同一个数可以被重复选。只要把树画对模板里的终止条件、for 循环边界、递归参数自然就出来了。反之树画错硬套哪套模板都会挂。5.2 如何快速判断题目的算法方向可以准备一个很简易的判断清单题目特征优先考虑的算法方向要求输出所有方案、所有路径、方案总数回溯配合剪枝若状态重复严重可转记忆化搜索只需要输出任意一个可行方案且局部选择不影响可达性可以考虑贪心或搜索需要求最大值/最小值且子问题有重叠动态规划优先需要求最大值/最小值且很容易证明“局部选择不会吃亏”贪心可以尝试解空间可以被描述成“每步从有限候选中挑一个”不管用什么算法先画决策树这个表不覆盖所有情况但它能帮初学者在早期节省大量犹豫时间。5.3 把“背模板”变成“复盘模板”真正有用的模板不是网上的标准代码而是你自己在画完树后总结出来的套路。比如回溯的模板骨架可以总结为确定递归参数哪些信息会随着选择变化哪些信息全局不变确定结束条件是走到叶子节点还是中途满足某个条件也能成为解确定循环范围这一层能选的候选集是什么确定剪枝规则什么时候直接继续什么时候直接返回确定状态还原用什么数据结构保存选择递归后如何恢复。每次刷完一道回溯题可以花两分钟复盘这五件事。下次遇到类似题型时你调用的不是一段代码而是一套思考清单。这样比背十道题的模板更有用。5.4 常见卡点和排查链路如果你在刷题过程中遇到问题建议按照下面的顺序排查而不是直接怀疑自己不会递归。如果输出结果重复是否允许重复组合如果不允许需要保证每次循环从start开始而不是每次都从头开始。是否使用used数组标记了已选元素全排列去重时既要看当前位置是否用过还要处理原数组中重复元素的问题通常需要排序后再剪枝。如果运行超时先检查决策树的分支数。分支如果高达 n 的 n 次方说明决策方式可能有问题。有没有剪枝条件比如当前和已经超过目标值就可以提前 return。是否存在大量重复子问题如果有把它从普通回溯改成带备忘录的 DFS看看是否快很多。是否在 for 循环里复制了超大数组复制数组本身就会带来很大的隐形开销。如果结果为空检查起点和终点的状态定义是否一致。检查结束条件是index len(nums)还是path 长度 k检查目标值在递归中是否被错误修改了。如果答案少了或重复检查撤销选择是否完整。尤其是递归函数里有提前 return 的分支容易漏掉pop()。检查是否在错误层级更新了全局变量。如果用“传路径副本”的方式注意空间复杂度是否能接受。5.5 一个小闭环先回溯后贪心刚才说到“贪心 回溯”是 LeetCode 里两座大山。但真正适合小白的一条路线不是开盘就分门别类地刷 500 道而是先用几道题把“暴力搜索”建立起来再从暴力搜索中看优化的机会。比如“跳跃游戏”这一类题你完全可以先写一个 DFS尝试从位置 0 跳到能跳到的每个位置看能不能到终点。这个 DFS 很可能超时但你能清晰看到“大量重复的子问题”同一个位置可能从不同前置位置到达。这时候你才意识到我需要的不是具体走法而是“该位置是否可达”以及“可达范围的最右值”。于是你自然会被引导到更高效的贪心或 DP 思路。先回溯再贪心不是一个刷题计划的顺序建议更是一种思维路径。它让你知道贪心不是从天上掉下来的灵感而是在穷举之后对决策树结构有了更深理解才敢做删减的产物。所以当你下次遇到一道看起来像回溯又像贪心的题时不用急着翻题解。先画树再问自己这道题必须把整棵树走完吗如果只走一条最特殊的分支这种偷懒会不会漏掉正确答案回答完这两个问题你离独立解出题就不远了。