企业官网建设流程全解析

提到回溯和贪心，很多刷 LeetCode 的小白第一反应是“又要背模板了”。网上模板确实不少，但套模板时总会出现各种问题：回溯写出来超时、结果重复，贪心“感觉对了”却过不了样例。如果只是背模板，你很难判断什么时候该用哪个、剪枝剪在哪里、为什么“局部最优”能拼出“全局最优”。

这篇文章不打算再给你一份万能模板，而是想把两个思维模型讲透：

• 回溯本质上是深度优先地遍历一棵决策树；
• 贪心本质上是在每一步决策时，只走当前看起来最优的那个分支。

理解了这两个模型后，你再看 LeetCode 上的回溯题和贪心题，会发现它们不再是一道道需要死记的题，而是一类能够用同一套思维去拆解的题。文章会用经典题目做例子，给你一套从画决策树到写代码、再到测试验证的完整流程，最后附上适合新手的刷题路线。

先给一个基础判断：遇到“列出所有方案”“判断是否存在可行方案”这类题目，优先想回溯；遇到“求最大最小值”“最优化问题”而且你能够证明局部最优可以推出全局最优时，再考虑贪心。这两条判断标准看似简单，但比背几十个模板更实用。

1. 回溯与贪心核心能力速览

先建立一个整体认知。回溯和贪心不是互斥的关系，它们都可以看作是“在一棵决策树上寻找答案”的方法，区别在于你怎么处理这棵树。

从表格可以看出一件事：回溯拥有更大的搜索空间，所以算法设计里“剪枝”特别重要；贪心的搜索空间小，但代价是“局部最优不一定等于全局最优”，所以证明比实现更难。

2. 为什么把回溯和贪心放在一起讲

不少刷题攻略会把回溯和贪心分成两个完全独立的章节，但我建议把两者放在一起理解，因为它们本质上在回答同一个问题：在一棵决策树上，你怎样走到目标叶子节点？

回溯的做法是“不知道哪条路是对的，那就全部走一遍”。它每一步都保留所有分支，如果发现当前路径不可能通向答案，立刻撤销选择、退回上一个节点，再尝试其他分支。这个“退回再走”的动作就是回溯。

贪心的做法则是“我认为当前最好的分支就是最优解的一部分，所以其他分支我都不看了”。它每一步都选择一个局部最优动作，然后把问题规模缩小，继续下一步。因为没有搜索其他分支，贪心通常非常快。

两者之间存在一个非常直观的联系：贪心可以理解成“剪枝剪到极致”的回溯。

如果你在回溯遍历决策树时，每一层都能证明只有某一条分支可能产生最优解，那么其余所有分支都不需要遍历。这时候回溯就退化成了一条直线往下走的贪心。反过来，如果贪心策略没法证明“局部最优能推出全局最优”，你就不能贸然只用单分支搜索，而要退回回溯或者动态规划把所有可能性覆盖住。

这个视角能帮你解决刷题时最常遇到的判断问题：为什么这题不能用贪心？因为你无法证明剪掉的那些分支里没有最优解。

另外还有一个进阶概念叫“反悔贪心”，比如某些任务调度题，先按一个规则贪心选择，如果后面发现之前的选择不划算，就通过替换之前的选择来修正结果。这类题的思维本质仍然是“维护一棵动态决策树”，只是每次替换相当于在树上做一次分支切换。

3. 环境准备与刷题起点

LeetCode 刷题不需要复杂的本地环境，但建议你至少把以下内容准备好，提高调试效率。

3.1 语言选择

回溯代码往往需要递归和列表操作，Python、Java、C++、Go 都可以，不需要局限于某一门语言。这里用一个比较重要的标准：选你最熟悉、写递归最顺手的语言。

如果你刚开始刷题，Python 是一个不错的选择，因为代码量少、可读性高，能让你把注意力放在算法思想上而不是语法细节上。下面所有示例代码也以 Python 为例。

3.2 本地调试环境

LeetCode 网页编辑器可以用，但遇到回溯这种需要反复检查递归过程的题目，本地 IDE 会更方便。推荐你准备一个 Python 环境，至少能够执行以下流程：

# 建议使用 Python 3.8 以上版本 python --version # 如果本地没有 pytest，也可以直接写 if __name__ == "__main__" 测试

本地调试时，把 LeetCode 的类方法复制到本地，再写几组测试数据。例如：

from typing import List class Solution: def canJump(self, nums: List[int]) -> bool: max_reach = 0 for i, jump in enumerate(nums): if i > max_reach: return False max_reach = max(max_reach, i + jump) return True if __name__ == "__main__": s = Solution() print(s.canJump([2, 3, 1, 1, 4])) # 预期 True print(s.canJump([3, 2, 1, 0, 4])) # 预期 False

3.3 通过数据规模猜算法

拿到一道题，先看数据范围，再猜可能的算法方向，这是一个非常实用的刷题技巧。

这个表不是绝对的，但能帮你在“用回溯还是用贪心”之间做第一轮判断：如果数据规模很大，裸回溯大概率超时，要么剪枝能力极强，要么这题本身就暗示你应该使用贪心或者动态规划。

4. 回溯：把决策树画出来，代码自然就出来了

很多新手写回溯时，卡住的点是“不知道递归函数里要传哪些参数”。其实这个问题不应该靠猜，而应该靠画决策树解决。先看一个具体例子。

LeetCode 494 目标和，题目大意是：给定一个非负整数数组 nums 和一个目标整数 target，你可以给每个数字前添加+或-，问有多少种方法可以让所有数字相加后等于 target。

比如nums = [1, 1, 1, 1, 1]，target = 3，答案就是 5。

这道题为什么适合回溯？因为每个数字只有“取正”和“取负”两种选择，最终要列出全部符号方案。你完全可以画一棵二叉树：

• 第一层是第一个数，左分支取正，右分支取负；
• 第二层是第二个数，左分支取正，右分支取负；
• 依次类推，直到处理完所有数字。

这棵树一共有 n 层，每一层有两个分支，所以叶子节点数是 2^n。每个叶子节点上的“累计和”就是一条完整符号方案的最终结果。如果累计和等于 target，说明这条路可行。

画完这棵树，你已经知道递归函数应该怎么设计了。树的深度就是数组下标，从 0 走到 n，每一层对应一个数字；递归里的状态是“当前处理到第几个数字”和“当前累计和”。于是代码几乎是看图翻译出来的：

from typing import List class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: n = len(nums) ans = 0 def dfs(i: int, cur: int) -> None: nonlocal ans if i == n: if cur == target: ans += 1 return # 当前数字取正 dfs(i + 1, cur + nums[i]) # 当前数字取负 dfs(i + 1, cur - nums[i]) dfs(0, 0) return ans

这就是“先画树，再写代码”的优势：你不会背模板，而是用树的结构推导出递归参数和分支逻辑。

4.1 回溯的三要素

把上面的代码抽象一下，回溯通常由三个部分组成：

• 路径：记录已经做的选择，在目标和题目里就是到目前为止的累计和，在其他题目里可能是一个列表。
• 选择列表：当前可以尝试的所有选择。目标和题目里只有正负两种；全排列题目里是还没用过的数字；组合题目里是当前下标之后的数字。
• 结束条件：到达决策树底部时判断当前路径是否为可行解。

具体到实现中，回溯的框架通常是：

def backtrack(路径, 选择列表): if 满足结束条件: 结果.append(路径[:]) return for 选择 in 选择列表: 做选择 backtrack(路径, 更新后的选择列表) 撤销选择

这里的关键点有两个。

第一，结果.append(路径[:])必须复制路径，如果直接 append 路径对象，后续撤销选择时会把这个对象的值改掉，最终所有结果都变成空列表。

第二，递归之后必须撤销选择，这是“回溯”这个词的来源。调试时如果发现答案异常，优先检查是否漏掉了撤销这一行。

4.2 从画树到剪枝

画完整棵树只是第一步。数据规模一大，2^n 的叶子节点很快会超出时间限制，这时就要想办法剪枝。剪枝的本质是：在遍历过程中发现某些分支根本不可能产生合法解，就提前停止往下递归。

来看 LeetCode 39 组合总和。题目要求从 candidates 中找出所有组合，让这些数字的和等于 target，每个数字可以重复使用。输入candidates = [2,3,6,7]，target = 7，需要返回[[2,2,3],[7]]。

如果你直接暴力枚举每一种数字排列，会出现大量重复结果，比如[2,2,3]和[2,3,2]和[3,2,2]都会被算作不同组合，但题目要求组合而不是排列。

解决思路是画树时给“选择列表”加一个顺序约束：每次递归都只从当前下标开始选择，而不是从 0 开始。这样同一组数字只能被按照递增下标的方式取出来，天然避免了排列重复。

同时，因为候选数组是正整数，如果当前数字已经大于剩余需要凑的和 rest，后面的数字只会更大，可以直接结束当前循环，这就是一个高效的剪枝：

from typing import List class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() ans = [] path = [] def dfs(begin: int, rest: int) -> None: if rest == 0: ans.append(path[:]) return for i in range(begin, len(candidates)): # 剪枝：当前数字已经比剩余和还大，后面的数字更大 if candidates[i] > rest: break path.append(candidates[i]) # 允许重复使用当前数字，所以下一次递归仍然从 i 开始 dfs(i, rest - candidates[i]) path.pop() dfs(0, target) return ans

这就是一个很常见也很有代表性的回溯剪枝过程。你画决策树时，如果某个节点的剩余和 rest 已经小于 0，或者当前候选值已经大于 rest，那么以它为根的整棵子树都没有存在必要，直接 return 或 break，代码的性能会明显提升。

4.3 回溯题目怎么验证

写完回溯代码后，建议按下面的过程验证，而不是只跑一个示例就提交。

先拿题目自带的小样例手动推演一遍，确认输出正确；再构造一个极端小数据，比如 n=1 或 n=2，验证边界条件；之后观察复杂度，如果搜索空间较大，可以打印递归进入次数，确认剪枝是否生效；最后再提交到 LeetCode 跑完整测试集。

如果超时，不要急着改语言或换算法，先看决策树有多少冗余分支。比如组合类题目没加 begin 参数导致重复搜索、子集去重题没排序就跳过、目标和类题目没有加记忆化，这些都是常见的超时原因。

5. 贪心：局部最优如何推出全局最优

贪心和回溯相反，它不需要遍历完整的决策树，每一步直接选定当前看起来最优的分支。贪心的难度不在代码实现，在于判断“这个贪心策略是否正确”。

5.1 贪心的适用条件

贪心能成立通常需要满足两个性质：

一是贪心选择性质：每一步的局部最优选择可以包含在某个全局最优解中。换句话说，你选择当前最优分支，不会丢掉最终答案。

二是最优子结构性质：一个问题的最优解包含其子问题的最优解。也就是说，你先做出一步选择后，剩下问题的最优解仍然可以用同样的贪心策略解决。

很多面试题不会直接告诉你“这题用贪心”，而是靠你分析这两个性质。分析不出来时怎么办？最直接的方法是把当前局部最优的决策带入一个随机测试，尝试构造反例，如果构不出来，再尝试用交换论证去证明。

5.2 跳跃游戏示例

LeetCode 55 跳跃游戏：给定非负整数数组 nums，你最开始位于数组的第一个下标，每个元素代表你在该位置可以跳跃的最大长度，判断你是否能够到达最后一个下标。

这道题看起来像是模拟每一步跳多远，实际上有一个非常漂亮的贪心解法：维护一个“当前能到达的最远位置”max_reach，从左到右遍历数组，每到一个位置，都尝试用i + nums[i]更新跳跃范围。如果遍历到的下标已经超过了 max_reach，说明前面的位置无法跳到这里，返回 false；如果 max_reach 已经覆盖到最后一个下标，返回 true。

from typing import List class Solution: def canJump(self, nums: List[int]) -> bool: max_reach = 0 for i, jump in enumerate(nums): if i > max_reach: return False max_reach = max(max_reach, i + jump) return True

这个解的贪心选择在哪里？在位置 i，你不关心具体要跳到哪个格子，而是“尽量把可达边界推到最远”。从直觉上看，可达边界扩大得越远，越容易覆盖到终点，所以每次选择最大扩展不会比其他选择差。

更严格的证明思路是交换论证：假设某个全局最优解从位置 i 跳到了位置 j，而当前位置能跳到的最远位置是 f，且 f 一定不小于 j。那么把“跳到 j”换成“跳到 f 或能到达 f 的路径”，不会减少后续可达范围。因此每一步把范围推到最大是安全的。

这里的“局部最优”不是一步一步模拟跳跃，而是在扫描过程中不断扩张可达区间。这是区间类贪心的常见思路，类似的还有无重叠区间、用最少的箭引爆气球等题目。

5.3 贪心不成立的反例

为了说明证明的重要性，再举一个经典反例：零钱兑换。

假设有面值 1、3、4 的硬币，要凑 6 元。如果按“尽量用大面值”的贪心策略，第一步选 4，剩下 2 只能用两张 1，一共需要 3 枚硬币，答案并不是最优的，因为最优解是 3 + 3，只需要 2 枚硬币。

这就是典型的“局部最优推不出全局最优”。所以在做最优化题目时，如果只是感觉贪心对、但没有构造证明，很容易在隐藏测试用例上翻车。遇到这种情况，你需要的不是贪心，而是动态规划这样能覆盖整个决策空间的做法。

5.4 区间贪心、排序与决策树

区间类贪心题目有一个很固定的套路：排序 + 一次扫描。比如用最少数量的箭引爆气球，按右端点排序后，尽量把箭射在当前区间的右端点，这样能让箭覆盖最多后续区间。这类题每一步的局部最优就是“当前箭能覆盖到的位置尽量靠右”，这种选择同样不会让结果更差。

从决策树视角来看，排序的作用是让候选分支出现一种单调性。排序之后，你能够通过第一个可行分支立刻确定最优解，从而把回溯要考虑的 O(n!) 种选择压缩成 O(n log n) 处理。理解这一点很重要，否则你只会在代码里“背下排序这步”，却不知道为什么必须排序。

6. 回溯与贪心：从决策树看它们的共性与差异

把两个算法放在一起复盘，更容易看到全貌。

回溯对应的是“完整决策树 + 深度优先遍历 + 撤销选择”。它不假设哪条路更好，所以能保证不遗漏可行解，代价是复杂度通常很高。优化方向集中在剪枝和去重。剪枝去掉的是“不可能通向答案的子树”，去重去掉的是“结构重复的子树”。

贪心对应的是“决策树 + 只走局部最优分支”。它假设某一层的最优分支已经足够，于是每一层只需要向下走一个节点。这种策略能否成功，取决于你是否真的剪掉了所有非最优子树，而这个剪枝是否安全，必须通过证明或反例来验证。

所以你可以用一句不太好听但很实用的话概括：贪心就是过度剪枝的回溯，只不过它剪枝剪得有理有据；回溯是不太敢剪枝的搜索，它靠遍历保全正确性。动态规划则介于两者之间，它用状态定义把重复的子树合并掉，属于“把树的节点进行记忆化压缩”的做法。

有了这个统一认知，以后你遇到一道新题，就可以沿着一条思考链路走：

1. 这题是不是要画决策树？
2. 是不是需要把所有可行解都列出来？如果是，先想回溯。
3. 如果只要求最值，能不能证明某一类分支一定不优于另一类？能证明就贪心，不能证明就考虑动态规划覆盖全状态。
4. 如果数据规模很小，回溯是安全的兜底方案；如果数据规模很大，回溯基本超时，必须从贪心或 DP 里寻找更优解法。

7. 常见卡点与排查方法

下面这些问题是刷回溯和贪心时最常见的，整理成一张排查表，方便你遇到问题直接对照。

其中“题解能看懂，自己写不出”是最常见的痛点。解决办法只有一个：不要直接看题解代码，先自己画树。画完树你会发现递归函数要哪些参数、结束条件是什么、撤销选择在哪一行，这些都不再需要背。

8. 从模板到思维：刷题路线与最佳实践

如果你准备系统刷回溯和贪心，建议不要上来就做 Hard 题，而是按下面的路线走。

8.1 回溯入门阶段

先练最基础的三类问题：组合、排列、子集。它们结构相似，但决策树形态不同，非常适合用来理解回溯的“选择列表”差别。

组合、子集、全排列这三类题目如果连续刷，你会发现它们的搜索树长得很类似，只是“选择列表”的定义不同。建议按“组合 -> 子集 -> 全排列”的顺序练习，因为前两个不需要 used 数组，更容易把注意力放在树结构上。

8.2 回溯进阶阶段

刷过基础题目后，再练习这些更综合的题：

• LeetCode 22 括号生成：用左右括号剩余数量控制分支合法性；
• LeetCode 17 电话号码的字母组合：把字符串和映射当成选择列表；
• LeetCode 79 单词搜索：在二维网格上做带路径标记的 DFS；
• LeetCode 131 分割回文串：把切割点当作决策树的每一层；
• LeetCode 51 N 皇后：用坐标冲突判断剪枝；
• LeetCode 494 目标和：从回溯出发，理解如何改成记忆化搜索。

这个阶段的核心目标是培养“剪枝敏感度”。每道题都问自己四个问题：决策树长什么样？每一层对应什么选择？哪些分支可以被安全剪掉？去重需要保证什么顺序？

8.3 贪心入门阶段

贪心题目给新手的感觉通常是“每道题思路都不一样”，很难一劳永逸。但从题型来看，可以分成几类。

做贪心题时，建议每道题都强制自己完成一步“证明尝试”。即使写不出来完整证明，也要至少尝试构造反例，问自己：如果每次都选看起来很贪心的方案，有没有可能漏掉最优解？

8.4 复盘与周赛使用

刷题不只是为了过题，还要形成自己的复盘记录。建议每道题记录三部分内容：

• 这题的决策树或贪心选择是什么；
• 第一次做错或卡住的原因是什么；
• 如果再遇到同类题，第一步应该先看什么。

参加 LeetCode 周赛时，这套复盘习惯能显著提高效率。周赛前两题经常出现贪心或简单回溯，第三四题则可能出现更复杂的区间贪心、反悔贪心、DFS + 剪枝。如果你能快速判断出“这道题是决策树结构”或者“这道题可以用贪心扫描”，就已经解决了一大半问题。

9. 总结与下一步

回溯和贪心的区别不在代码，而在决策树的处理方式。回溯遍历完整决策树，用撤销选择保证正确性，靠剪枝保证性能；贪心只沿局部最优分支走，用证明保证不会走错。

建议你先拿 LeetCode 77 组合或 494 目标和做一次完整的画树练习：把树画出来，标出路径、选择列表和结束条件，再写代码；然后把 55 跳跃游戏和 452 用最少数量的箭引爆气球做一次贪心证明练习，尝试向自己解释“为什么局部最优不会丢解”。

最容易踩的坑是“刷完回溯立刻背模板，刷完贪心立刻凭感觉提交”。模板只是结果，不是思维过程；感觉只是起点，不是正确性依据。真正值得投入时间的是画树、剪枝、构造反例和交换论证这几项基本功。

把这套方法练熟之后，你会发现自己不再需要依赖题解里的固定模板，看到题目时脑子里会自动浮现出一棵树，或者一个能解释为什么局部最优可以通向全局最优的证明过程。这个能力，比记住几十道题的模板要重要得多。