我常在面试和带人的时候被问到一个问题DFS深度优先搜索和回溯到底是不是同一个东西被问得多了我发现大家真正卡住的不是定义本身而是递归里那句path.pop()为什么非写不可。这篇文章想把 DFS 和回溯的基础一次讲透——从为什么会想到这样搜索到递归和栈在背后到底做了什么再到什么时候需要撤销状态。内容适合刚开始刷算法题、看到回溯就头大的同学也适合那种能 AC 模板题、但换个场景就写不明白的人。先给一个我常用的速记深度优先搜索是一种遍历方式它只管沿着一条分支尽可能往下走走不动了就退回来换一条而回溯是建立在深度优先搜索之上的一套解题策略核心在于尝试、检查、还原。后面所有代码和例子都围绕这两句话展开。1. 先建立直觉迷宫、岔路和不服就回头的行为模型1.1 迷宫实验人天生就会DFS想理解 DFS不用先看代码先想想你在迷宫里的行为。假设你站在一个岔路口面前有三条通道你不知道哪条通向出口。大部分人的做法是先挑一条走一路向里遇到新的岔路再选一条直到走进死胡同或者找到出口。如果是死胡同你会沿着原路退回到最近的一个岔路口换一条没试过的路再走。这个行为里有几个关键点第一你尽可能深入第二走不通时你退回到最近的岔路口而不是回到起点重新来第三你需要记住哪些岔路已经试过。这三个特征恰好就是 DFS 的全部核心。退回到最近的岔路口这句话值得多说一句。迷宫里的最近岔路口在数据结构里就是栈顶。你每深入一层就把当前位置压进栈遇到死路就从栈顶弹出一个位置回到上一个状态。后进先出正好和你在迷宫里的原路返回一一对应。所以不要觉得 DFS 反直觉它其实是人类最自然的搜索方式只是换了个名字而已。1.2 深度优先到底优先了什么与广度优先的简单对比既然提到深度优先就必须和广度优先BFS做个对照否则你很难体会优先这个词的含义。举个很生活化的例子。假设你在找工作有两种打听策略。DFS 式的做法是逮住第一个朋友问他认不认识合适的人他说不认识那再问他认不认识可能认识的人于是一条线往下挖直到这条线索彻底断了再回头找第二个朋友。BFS 式的做法是先把所有朋友都问一遍收集一圈线索再去逐个联系这些线索提供的人像水波一样一圈圈扩散。两种策略没有绝对的优劣。DFS 的空间占用通常更小因为它只需要保存当前这条路径上的状态复杂度约等于搜索深度BFS 则需要保存一整层的信息复杂度约等于搜索宽度。但 DFS 找最短路径很吃亏因为它走到底才回头很可能先找到一条绕远的路却不自知BFS 一层层推进第一次到达目标就是最短路径。对比维度DFSBFS搜索策略纵深优先一条路走到底层次推进逐层扩散底层结构栈或递归栈队列空间开销约等于深度 O(depth)约等于宽度 O(width)适用场景路径枚举、回溯、连通性检查最短路径、层级遍历在实际刷题里看到枚举所有方案所有路径棋盘连通块这类需求优先想 DFS看到最短最少步数这类需求优先想 BFS。这个区分虽然朴素但能帮你把大多数题的第一思路定下来。2. 从递归到系统栈DFS背后的运行机制2.1 函数调用栈递归为什么天然契合DFS很多人学 DFS 的第一步是背递归模板但背模板≠懂原理。递归之所以和 DFS 这么搭根本原因在操作系统给每个函数调用分配的那个栈帧。每次调用一个函数系统都会在调用栈上压入一个栈帧里面保存着本次调用的参数、局部变量以及返回后该接着执行的地址。当函数 return 时这个栈帧被弹出程序恢复到调用前的位置继续执行。这意味着什么意味着递归天然自带原路返回的能力。你递归深入一层就相当于在迷宫里走深一步递归返回一层就相当于退回到上一个岔路口。看一个最简单的例子二叉树前序遍历def preorder(node): if not node: return print(node.val) preorder(node.left) preorder(node.right)这段代码的执行路径是从根节点一路向左直到左子树为空然后返回到上一个节点进入它的右子树。整个过程中每个节点的左侧走完了接下来该走右侧这个信息就存在系统栈帧里。你什么都不用额外维护系统帮你把状态存好了。这就是递归写 DFS 最大的优势状态的管理交给系统你只关心当前节点怎么扩展。但它也有代价函数调用的开销比裸循环大而且在 Python 里递归深度默认限制在 1000 层左右遇到超深搜索树时容易直接 RecursionError。后面我会再提工程上怎么处理。2.2 显式维护栈的写法把系统隐藏的事拿到台面上递归虽然简洁但它把栈藏起来了。如果你想更清楚地看见 DFS 每一步在干什么或者想避免递归深度限制可以把栈显式地写出来。还是二叉树前序遍历用显式栈实现def preorder_iter(root): stack [root] while stack: node stack.pop() if not node: continue print(node.val) stack.append(node.right) stack.append(node.left)这里有一个很多人第一次看会晕的点为什么要先压右子树、再压左子树因为栈是后进先出我希望下一次弹出的是左子树那就得让左子树后进栈。如果你先压左再压右弹出的顺序就反了。递归写法和显式栈写法本质是等价的区别只在状态管理的方式。递归是系统用调用栈管理进行到哪一步显式栈是你用一个数据结构自己管理接下来要访问谁。当你有额外的状态需要保存比如路径、已访问标记、当前选择了哪些元素显式栈往往更灵活也更适合工程环境。基础阶段可以先用递归理解 DFS遇到规模超出递归限制的题目再换显式栈。写法可读性状态管理典型问题递归高贴近搜索树结构系统栈帧自动保存递归深度受限显式栈稍低需要自己维护顺序自定义栈内存放扩展信息代码繁琐但可控3. 回溯的核心状态怎么构建、怎么还原3.1 全排列的执行过程一棵越走越窄的搜索树现在进入本文最关键的部分也是我被问得最多的部分回溯里为什么要撤销状态。用全排列做例子最合适因为它的搜索过程足够直观。给定数组[1, 2, 3]输出所有排列。搜索过程可以画成这样一棵树第一层什么都还没选选 1path [1]选 2path [1, 2]只剩 3 可选path [1, 2, 3]输出结果撤销 3撤销 2选 3path [1, 3]只剩 2 可选path [1, 3, 2]输出结果撤销 2撤销 3撤销 1选 2path [2]... 继续同样的过程每一层的可选元素越来越少因为已经选过的元素不能重复选。树的每一层就是递归调用的深度每一条从根到叶的路径就是一个排列。标准代码如下def permute(nums): res [] path [] used [False] * len(nums) def dfs(): if len(path) len(nums): res.append(path[:]) return for i, x in enumerate(nums): if used[i]: continue used[i] True path.append(x) dfs() path.pop() used[i] False dfs() return res这个模板你也许见过很多次但真正值得研究的是最后四行used[i] True、path.append(x)、递归、path.pop()、used[i] False。前两步是尝试后两步是还原。3.2 为什么必须撤销共享白板的故事很多人想不通递归返回后path里为什么还残留着下层添加的元素因为这个path不是每一层递归的私有副本而是大家共享的同一个列表。用一个比喻假设一个团队在同一个白板上写当前分支的选人名单。你带着白板进入下一层写上选 2返回时白板上仍然写着选 2。下一轮循环你想尝试选 3如果直接写上去白板会变成选 1、选 2、选 3——这根本不是当前路径的真实状态。所以你在离开这一层之前必须把刚写的选 2擦掉让白板恢复成进入这层之前的样子。path.pop()擦掉的是路径used[i] False擦掉的是用过标记。这两个操作配合起来才把整个全局状态恢复原状。这也是回溯这个词的来历你沿着路径往深处探发现这个分支走完了就要原路退回把路上做的修改一件件撤销。这里有个细节值得点出来如果你把路径以path [x]这种新建列表的方式传入下一层那确实可以不用pop()因为每层拿到的都是全新列表天然隔离。但这样做有两个问题一是每次都要拷贝整个路径时间开销大二是状态分散在各层的参数里调试时不直观。基础阶段我更建议走共享列表 手动撤销的路线它能强迫你理解状态的来龙去脉。3.3 不恢复状态会怎样故障现场还原为了让你确信撤销不是可选项我描述一下把撤销代码删掉会发生什么。如果只删掉path.pop()递归返回后path里已经包含了所有元素长度直接等于len(nums)。下一轮循环再path.append(x)长度更长了永远不会满足len(path) len(nums)这个等式因为已经超过结果就是程序不断递归直到深度超限或者输出大量长度超标的错误路径。如果只删掉used[i] False情况稍隐蔽一点由于用过标记永远为 True后续分支里很多可选元素被跳过最终你拿到的排列会少一大半而且顺序错乱。我见过新手在调试器里盯着path看了半天始终想不明白为什么我明明撤销了上一层path 里还有上一轮的值。原因就一个path是共享引用你在函数体里操作的是同一个列表而不是某个局部副本。想验证这一点很简单在每个递归函数入口加一行print(id(path))你会发现所有层的 id 完全相同。4. 剪枝把无用的分支挡在递归之前4.1 可行性剪枝当前状态已经没有希望就走人纯 DFS 是一个很笨的搜索器它会把所有分支都走一遍。而回溯算法的实用价值很大程度上靠剪枝体现在递归进入某个分支之前就判断这条路已经没戏直接掉头。最典型的例子是组合总和问题。给定候选数组和一个目标值找出所有和为目标值的组合。标准回溯里通常会写def combination_sum(candidates, target): res [] path [] def dfs(start, remain): if remain 0: res.append(path[:]) return if remain 0: return for i in range(start, len(candidates)): path.append(candidates[i]) dfs(i, remain - candidates[i]) path.pop() dfs(0, target) return res注意这里的if remain 0: return。当剩余目标值变成负数说明当前路径已经加过头了无论后面怎么选都不可能归零直接返回。这就是可行性剪枝提前终止注定失败的路径。如果先把candidates排序还能更进一步。因为排序后一旦remain - candidates[i] 0后面更大的元素更凑不上break掉整层循环连剩余分支都跳过。4.2 重复元素的同层去重排序以后同层跳过为什么有效组合总和还有一种变体候选数组里包含重复数字而且每个数字只能用一次。如果你的搜索列表是[1, 2, 2, 3]不做处理就会输出重复的组合因为两个2被当成不同元素。处理办法是先排序然后在循环里加一行if i start and candidates[i] candidates[i - 1]: continue这一行的关键在i start很多教材直接写成i 0那是错的。start是当前递归层的搜索起点i start表示当前这个位置不是本层第一次选数。如果前一个相同的数已经在同一层被完整探索过那么当前这个数只会生成重复分支跳过。想想搜索树的结构就明白了。[1, 2(第一个), 2(第二个), 3]排序后同一层循环里第一次选中2时i start这个分支要保留等它递归完返回循环走到第二个2i start且值相等说明这是同一个位置上的重复选择直接跳过。这个技巧在组合总和 II、全排列 II 里反复出现值得背熟。但要注意全排列的去重条件不同。排列问题里重复元素的去重通常写成if i 0 and nums[i] nums[i - 1] and not used[i - 1]因为排列需要从 0 开始扫判断依据是前一个相同元素是否已经用在本层而不是start。去重逻辑和问题形态强相关别套错模板。4.3 剪枝不是越多越好先想清楚会不会误伤看到剪枝很香有人会在所有 DFS 里疯狂加各种提前 return。我的建议是基础阶段先做两类最保险的剪枝一类是边界剪枝比如数组下标越界、剩余目标值小于 0另一类是重复剪枝也就是上面说的同层去重。至于那些依赖业务语义的剪枝要想清楚会不会误伤。举个例子你为了减小搜索量在路径长度还没到目标长度时就按字典序最小剪掉一部分可能就把唯一解剪没了。剪枝的本质是用这条路不可能产生答案的判断换取分支数量下降。判断一旦下错正确答案就丢在递归之外了。所以每次加剪枝条件时我都习惯在纸上写一个反面例子专门验证这个条件不会砍掉合法解。5. 三种典型形态排列、组合、网格连通5.1 排列型used数组决定每一步能选什么排列问题的特点是顺序有意义[1,2]和[2,1]是两个不同答案。所以每一层递归都需要从数组开头扫起用used数组记录哪些元素已经出现在当前路径里。全排列的完整代码在第三节已经给过这里不再重复。我只强调一点排列型回溯的搜索空间是n!级别当n超过 10 左右完整枚举所有排列就已经很吃力了。如果题目问你的是第 k 个排列之类千万别真的把所有排列生成出来那是另一类数学题要用康托展开或者逐步定位的思路。排列型还有一种常见变体字符串的全排列比如字母去重排列。套路完全一样只是把nums换成字符数组然后记得先排序再做同层去重。5.2 组合型startIndex 防止回头重选组合问题的特点是顺序无意义[1,2]和[2,1]是同一个答案。为了让搜索不产生这两种重复组合型回溯从不在循环里回到已经走过的位置而是用一个start变量限定当前层的起点。看一个最基础的问题从 1 到 n 中选 k 个数输出所有组合。def combine(n, k): res [] path [] def dfs(start): if len(path) k: res.append(path[:]) return for i in range(start, n 1): path.append(i) dfs(i 1) path.pop() dfs(1) return res这里的关键是递归调用传i 1而不是固定的start 1。因为当前层选了i下一层只能从i 1开始选这样[1,2]和[2,1]里只有前者会被生成。对比一下排列和组合的循环起点排列里每层都从0开始配合used去重组合里每层从start开始靠start去重。这个差异可以直接对应到代码里for循环的写法上如果在做题时不知道自己该用哪种先判断顺序是否有意义思路会清晰很多。5.3 网格型标记访问替代恢复状态还有一大类 DFS 不走数组选数而是在二维网格上蔓延比如岛屿数量问题。给定一个由1陆地和0水组成的二维网格数一数岛屿的数量。思路很简单遇到一个1就把它所在的整个连通块淹没计数加一继续扫描网格直到扫完。def num_islands(grid): if not grid: return 0 m, n len(grid), len(grid[0]) def dfs(i, j): if i 0 or i m or j 0 or j n or grid[i][j] 0: return grid[i][j] 0 dfs(i 1, j) dfs(i - 1, j) dfs(i, j 1) dfs(i, j - 1) count 0 for i in range(m): for j in range(n): if grid[i][j] 1: count 1 dfs(i, j) return count网格型 DFS 和回溯最大的不同是它不需要恢复状态。原因也很好理解回溯的目的是枚举所有不同的方案一个选择做完要腾出位置给其他选择而网格 DFS 的目的是把已经访问过的格子标记掉避免后续重复进入这个标记是单向的、永久的。但并不是所有网格题都不用恢复。比如单词搜索问题要求判断一个单词是否存在于网格中同一个格子在一条路径里只能使用一次。这时你就需要一个visited数组并且在做完四个方向的搜索后把visited[i][j]恢复成 False因为从另一个起点出发时这个格子可能又被合法地作为路径的一部分。判断标准还是那句话分支之间是否存在共享状态需要复位的需求。三种形态可以浓缩成一句记忆排列用used保证不重不漏组合用start限制搜索区间网格用标记代替回溯。做题时先判断属于哪种再决定状态怎么设计。6. 调试与排错让看不见的搜索树现出原形6.1 打印缩进法在递归的入口和出口打卡DFS 的调试一度让我很头疼因为它不像普通循环那样能一步步看清变量变化。后来我养成了一个习惯在递归函数里按层级打印状态用缩进表示递归深度。def dfs(level): indent * level print(f{indent}enter: path{path}) if len(path) len(nums): res.append(path[:]) print(f{indent}found: {path}) return for i, x in enumerate(nums): if used[i]: continue used[i] True path.append(x) print(f{indent}choose {x} - {path}) dfs(level 1) path.pop() used[i] False print(f{indent}back: path{path})跑一遍输出的大致样子是这样的enter: path[] choose 1 - [1] enter: path[1] choose 2 - [1, 2] ... found: [1, 2, 3] back: path[1, 2]每次choose表示进入更深一层每次back表示这一层的所有尝试已经结束。把整个输出按缩进排开其实就是一棵完整的搜索树。我到现在遇到复杂的回溯题第一件事还是加打印把树看清楚再动手优化。6.2 引用传参的大坑为什么结果全是空列表新手写 DFS 最容易踩的坑就是把结果直接res.append(path)。表面看没问题最后返回的结果却是一堆空列表或者全是同一个排列。原因我在前面提过path是共享的可变对象res里存放的是对它的引用而不是快照。你每次path.append和path.pop改的是同一个列表等递归结束所有res里的元素都指向同一块内存最后看到的就是最后一次回溯后的空列表。正确写法是res.append(path[:])切片会创建一个新列表把当前路径的内容复制一份存进去。这个[:]是回溯题里最常见的细节之一凡是把临时列表加入结果集的地方都要想一下是否应该拷贝。还有一个小坑和参数传递有关。如果你在递归函数里直接修改了传入的可变参数比如nums.remove(x)删除一个元素后再递归等递归返回时nums已经被改变了下一轮循环的索引完全对不上。基础阶段我建议尽量只通过nums[i]读取元素、通过下标和路径列表来维护状态不要在回溯过程里原地修改输入数组否则很难恢复。6.3 三个我实际踩过的经典坑把这些年带人和自己遇到的常见问题汇总一下方便你对号入座。错误写法现象修复方式忘记path.pop()递归深度失控结果错乱在递归返回后立即撤销添加忘记used[i] False排列数量变少分支被错误跳过和path.pop()成对出现res.append(path)而非副本所有结果相同或为空改成res.append(path[:])上面这几个错误本质上都指向同一个问题递归是一种深入再返回的控制流返回时不会自动清理你手工改过的状态必须靠你自觉恢复。这也是为什么我一直强调理解状态恢复比背模板重要因为模板能告诉你哪里要写pop但不能告诉你为什么这里少写一行就会全错。6.4 验证自己的DFS代码是否靠谱写完之后怎么确认代码是对的我常用的办法是小数据人肉模拟 对照验证。先用最小的输入在纸上画出搜索树确认分支数和结果数。比如全排列[1,2,3]应该输出 6 个结果组合 C(4,2) 应该输出 6 个结果如果数对不上说明搜索树本身画错了。然后写一个最容易理解的暴力枚举版本比如用 Python 的itertools.permutations生成全部结果和你的 DFS 结果逐项比较。两者一致基本可以确定状态恢复和剪枝逻辑没有大问题。这些小工具不是为了偷懒而是给你一个标准答案来对照。一旦发现差异再用打印缩进法定位是哪一层、哪一个分支出了问题。三步走完一个回溯题的排错基本就结束了。说到个人体会我真正把 DFS 和回溯搞明白不是在背下模板那一刻而是某次调一个全排列题盯着终端里层层缩进的打印输出看了十分钟突然意识到每一层递归都对应一次选择和一次归还。从那以后我再也不怕什么排列组合变体题了因为我知道不管题目怎么换核心还是那棵搜索树、那两行状态恢复以及一个画清楚就能看明白的递归结构。如果你也正在这个坎上不妨少背几道题多画几棵树试试。