回溯这个坑我估计每个刷题的人都被它坑过不止一次。网上讲DFS的文章多如牛毛但大多要么是纯概念堆砌要么是代码甩脸看完“似懂非懂”自己一写就废。我自己也是从那种状态摸爬滚打过来的所以这篇准备换一种讲法——先把“为什么”这个层面掰开揉碎再给你能直接抄的模板和实战案例最后聊聊那些官方文档里不会写的调试心得和避坑技巧。这篇内容不是什么高深理论就是DFS深度优先搜索和回溯最核心、最基础的那点事配上能跑的代码适合刚接触算法、或者刷题刷到递归总是一头雾水的朋友也适合想回头把基础夯实的开发者。1. DFS的核心思想与回溯的本质1.1 从“走迷宫”理解DFS的遍历顺序深搜这件事用走迷宫来解释是最直观的。假设你站在迷宫的入口面前有几条岔路。DFS的策略特别简单粗暴选一条路一条道走到黑走不通了就退回到最近的分岔口换另一条路继续走。这个“退回分岔口”的动作就是“回溯”。好现在把迷宫抽象一下。迷宫的岔路口就是“状态”每条路就是一次“选择”。从入口出发不断选择、不断深入的过程就是深度优先搜索。而“走不通就回头”这个动作对应到代码里的表现就是一次函数调用返回之后恢复到调用之前的状态。这个过程也叫“状态重置”。很多初学者会把DFS和递归划等号严格说不对。递归是DFS最常见、最自然的实现手段因为函数调用栈天然就具备“向下深入”和“逐层返回”的特性。但DFS也可以用显式的栈来写稍后我会专门说这个。1.2 回溯决策树上的“撤销操作”回溯说白了就是在DFS遍历“决策树”的过程中一旦发现当前路径不可能产生有效解就撤销上一步的选择回到上层的另一个分支。画成图就是一棵不断分叉的树每个节点代表一个“当前状态”每条边代表“做出一个选择”叶子节点就是“最终答案”。我习惯把回溯的过程拆成三个动作选择在当前状态下确定下一步可以尝试的所有选项。递归选择一个选项把状态推进到下一个节点继续向下搜索。撤销当前分支探索完毕无论是得到答案还是走进死胡同要把状态恢复到进入这个分支之前的样子。这里最核心的就是“撤销”。很多人写回溯代码把选择做了、递归调了却忘了还原状态导致后面的分支拿到的是被污染的数据结果各种莫名其妙。这个动作之所以必须做是因为“决策树”的每个分支都是共享同一份状态空间的一条分支上的改动如果不撤销会串到另一条分支上去。我自己最开始学的时候脑子里就把DFS和回溯拆成两层DFS是遍历的“骨架”回溯是DFS在解空间搜索时用来“反悔”的“补丁”。理解到这个层面后面看排列、组合、子集这些经典题就是同一套东西换皮。2. 递归写法和显式栈写法两条腿走路2.1 函数调用栈天然的“回溯现场”递归实现DFS是大多数人最先接触的版本也是面试里最常被要求手写的版本。因为函数调用栈本身就是个“后进先出”的结构递归进多深就能回退多深完全不用自己维护状态。来看一个最基础的例子遍历一颗二叉树的所有路径。def dfs(node, path, result): if node is None: return # 做出选择把当前节点加入路径 path.append(node.val) # 到达叶子节点记录完整路径 if node.left is None and node.right is None: result.append(path[:]) # 注意这里要拷贝 else: # 递归深入左右子树 dfs(node.left, path, result) dfs(node.right, path, result) # 撤销选择把当前节点从路径中移除 path.pop()这里大家最容易撞墙的就是result.append(path[:])这行。如果你写result.append(path)最后得到的会是同一个列表的多个引用等路径回溯结束列表被清空result里存的全是空列表。这是回溯问题的第一个“经典大坑”。必须拷贝一份快照因为path在后续递归中会反复变化。有人会问为什么撤销这一步不放到递归函数开头做比如“先pop再进入下一层”这就要回到DFS的本质你必须先把当前节点所有的可能后续探索完才能离开这个节点。撤销语句的位置是在“当前分支的所有探索都结束之后”而不是“进入分支之前”。这个顺序感特别重要写多了自然就形成肌肉记忆了。2.2 显式栈当不想被递归深度压垮时递归实现虽然好写但有一个硬伤递归深度受系统调用栈限制。Python默认递归深度大概在1000层左右超出就抛RecursionError。虽然多数算法题不会让你递归那么深但如果你在做一些大规模图遍历、或者系统里写个非递归版本会更稳的工具显式栈就是必须的。显式栈的核心思想是自己用一个列表模拟调用栈栈里存的不光是“当前节点”还得存“当前处理到哪一步了”。这比递归要繁琐一些因为你要手动保存上下文。以二叉树中序遍历为例递归版本五行写完def inorder_recursive(root): result [] def dfs(node): if node is None: return dfs(node.left) result.append(node.val) dfs(node.right) dfs(root) return result显式栈版本长这样def inorder_iterative(root): result [] stack [] node root # 只要还有节点要处理就继续 while stack or node: # 一路向左把所有左子树节点压栈 while node: stack.append(node) node node.left # 弹出栈顶此时左子树已经处理完 node stack.pop() result.append(node.val) # 转向右子树 node node.right return result对比一下就能发现递归版本里的“函数调用”被替换成了“压栈”而“函数返回”对应的是“弹栈”。显式栈的优势是突破了递归深度限制而且能更精细地控制遍历过程——你可以随时暂停、随时恢复这在某些场景里非常有用。缺点是代码可读性差一些上下文管理要自己写容易出bug。2.3 递归函数参数设计的三个“潜规则”参数怎么设计是很多人写DFS的拦路虎。我总结下来有三个规律基本够用参数里放“当前状态”比如当前走到哪个节点、当前路径是什么、剩余可选范围是哪段。参数里放“目标信息”比如要找的目标值、约束条件、结果收集容器。尽量少用全局变量能传参就传参。全局变量在递归里很容易因为共享状态而互相污染排查起来很痛。拿一个场景举例求一棵二叉树所有“从根到叶子且和为target”的路径。状态参数就是当前节点和当前累积和目标信息是target和resultpath因为要回溯建议放在状态里而不是局部变量里。def path_sum(root, target): result [] path [] def dfs(node, cur_sum): if node is None: return path.append(node.val) cur_sum node.val # 叶子节点且满足条件记录结果 if node.left is None and node.right is None and cur_sum target: result.append(path[:]) else: dfs(node.left, cur_sum) dfs(node.right, cur_sum) path.pop() dfs(root, 0) return result注意这里的cur_sum我用的是“相加后传值”而不是“相加后原地修改”因为int在Python里是不可变变量传入下一层的就是一个全新副本完全不需要“加回去”的操作。这个特性反而是省心的地方。类似地字符串拼接传新值、tuple直接传引用但不可变都是好用的思路。3. 实战三板斧排列、组合、子集刷题和实际写代码里DFS出现频率最高的三类问题就是排列、组合和子集。这三类题本质上都是“从集合里选元素按不同条件收集结果”但细节差别很大。我们把它们放在一起对比着看理解会深很多。3.1 全排列状态重置的教科书案例先看全排列给定数组[1, 2, 3]要求输出所有排列每个数用一次顺序不同算不同结果。解法核心是维护一个used数组记录哪些数已经用过在每一层递归里都从头遍历所有数挑一个没用过的放进来递归到下一层回来之后再把它标记为“未使用”。def permute(nums): result [] used [False] * len(nums) path [] def dfs(): # 所有数都用完了path里就是一个完整排列 if len(path) len(nums): result.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 result这段代码最重要的就是末尾那两行path.pop()和used[i] False。path是当前排列的内容used是哪些元素已经被占用。只要有一个忘了恢复就会出现“第二个排列里少了一个数”之类的魔幻结果。很多人会问能不能不传startIndex答案是排列问题恰恰不需要startIndex因为每一层都要从头开始扫描所有元素只要那个元素还没被用过就行。while组合、子集问题里startIndex才是关键。这个区别一旦想明白排列和组合的区分就不会再搞混。3.2 组合与子集startIndex的妙用组合问题从[1, 2, 3]中选2个数输出所有组合[1,2]和[2,1]算同一个。这要求我们“不走回头路”因此需要用一个start参数保证只从当前位置之后的元素里继续选。def combine(n, k): result [] path [] def dfs(start): # 组合长度达到k记录结果 if len(path) k: result.append(path[:]) return # 从start开始逐个尝试后面的数字 for i in range(start, n 1): path.append(i) dfs(i 1) # 关键下一次从i1开始避免往前选 path.pop() dfs(1) return result这里的dfs(i 1)是核心。每一步选了i下一步就只能从i1开始天然避免了[1,2]和[2,1]这种重复组合。这比用used数组去重简单直接得多也是组合问题区别于排列问题的本质特征。子集问题和组合极其像唯一的区别是子集问题要收集所有节点的快照而不是只在叶子节点收集。也就是说每次递归进入一个新状态都把当前path记录一下。def subsets(nums): result [] path [] def dfs(start): # 每次进入这个函数当前path就是一个合法子集 result.append(path[:]) for i in range(start, len(nums)): path.append(nums[i]) dfs(i 1) path.pop() dfs(0) return result这三类问题放一起记排列关注“谁还没用过”所以每层从头扫描且依赖used组合关注“下一步从哪里开始”所以传start子集是在组合的骨架上多了一个“入口即记录”的动作。理解这个三角关系大部分排列组合类题目都能一眼定位到对应模板。3.3 去重为什么“排序剪枝”是标配组合、子集问题里还有一个高频延伸需求原数组里有重复元素要求结果不能有重复组合。比如[1, 2, 2]的子集如果直接用上面的模板会把[1,2]和另一个同样内容的[1,2]都算出来。标准解法是先排序再在同一层递归中跳过“和前一个值相同但前一个值没被使用”的选项。def subsets_with_dup(nums): nums.sort() result [] path [] def dfs(start): result.append(path[:]) for i in range(start, len(nums)): # 同一层循环里如果当前值和上一个值相同且上一个没被选入就跳过 if i start and nums[i] nums[i - 1]: continue path.append(nums[i]) dfs(i 1) path.pop() dfs(0) return result为什么nums[i] nums[i - 1]这个条件要写成i start而不是i 0因为“去重”去的是同一层分支之间的重复而不同层级里的重复值是可以同时存在的。拿[1, 2, 2]举例第一层选了第一个2进入到第二层后仍然可以选第二个2这形成的是子集[2,2]是合法且唯一的。而如果第一层选了第二个2就会和选了第一个2的分支产生重复这才需要跳过。判断条件是“同一层里是否已经选过相同值”而不是“全局是否出现过相同值”。i start就确保了判断范围只在当前这一个for循环内不会误伤下层递归里的重复选择。这个细节在面试里经常被追问能讲清楚的人很少但它恰恰是整个去重逻辑的钥匙。4. 剪枝与优化暴力搜索最后的倔强4.1 可行性剪枝和最优性剪枝DFS最招人诟病的点就是复杂度高。全排列是O(n!)子集是O(2^n)数据规模稍微上来一点裸奔的DFS直接就爆炸了。这个时候剪枝就是暴力搜索唯一的救命稻草。剪枝分两大类可行性剪枝从当前状态继续往下走无论如何都不可能到达合法结果直接返回。比如求组合总和等于target如果当前累积和已经超过target了后面的正数加进来只会更大不可能命中直接剪掉。最优性剪枝在一些求最优解的DFS里当前路径已经比已经找到的答案差了没有再往下走的必要。比如背包问题里当前重量已经超了不用继续递归。拿“组合总和III”来举例从1到9里选k个数使得和等于n。除了常规的start剪枝之外还能做两个可行性剪枝def combination_sum3(k, n): result [] path [] def dfs(start, cur_sum): # 剪枝1当前和已经超过目标后面只会更大 if cur_sum n: return # 剪枝2path长度超过k直接返回 if len(path) k: if cur_sum n: result.append(path[:]) return for i in range(start, 10): path.append(i) dfs(i 1, cur_sum i) path.pop() dfs(1, 0) return result这里cur_sum n的判断放在开头是典型的可行性剪枝。如果没有这个判断递归会一直深入到所有路径都遍历完才在长度判断时被拦下浪费大量计算。剪枝的本质就是用一句话挡住一棵子树值博率非常高。4.2 记忆化给DFS装个缓存如果DFS在递归过程中反复计算相同的子问题那就可以用记忆化——把已经算过的状态结果存起来下次直接取。最经典的就是“爬楼梯”这类题目。爬楼梯的DFS朴素写法是这样的爬到第n阶可以从n-1阶跨一步来也可以从n-2阶跨两步来所以f(n) f(n-1) f(n-2)。如果直接递归复杂度是O(2^n)n稍微大一点就跑不动了。def climb_stairs_dfs(n): memo {} def dfs(i): if i 2: return i # 如果这个状态已经算过直接用 if i in memo: return memo[i] memo[i] dfs(i - 1) dfs(i - 2) return memo[i] return dfs(n)这就是“带备忘录的DFS”。本质上它已经非常接近动态规划了区别只在于动态规划是自底向上递推而记忆化DFS是自顶向下递归。很多人学DP觉得难先把记忆化DFS练熟再转DP会顺手很多。4.3 边界条件最容易翻车的三个地方写DFS最容易翻车的边界条件我每次面试复盘都会反复提空输入的边界数组为空、target为0、根节点为None这些情况应该在递归外先兜底处理或者在递归入口处直接判断返回。递归终止条件的多种形式是“数组越界”“达到目标长度”“当前和等于目标”还是“节点为空”不同问题终止条件在代码里位置不同但核心原则是在“下一步可能会拿不到合法数据”之前就结束这一分支。结果快照拷贝时机把path放进result时必须用path[:]或list(path)拷贝一份。继续修改path不影响已经存入result的内容。很多人写着写着忘记这一步回头看一堆空列表就是这个原因。这三个坑我统称“回溯三件套翻车点”几乎每个新手都会踩一遍踩完才能长记性。5. 常见问题排查与调试实录5.1 死循环与无限递归递归函数如果缺少终止条件或者终止条件永远无法满足就会无限递归直到栈溢出。排查这种问题一般有两个技巧在递归函数开头打印当前状态观察它是否在重复访问同一个状态。给递归加一个最大深度限制用参数传进去超出就强制返回方便定位是在哪一层开始“转圈”。一个典型的场景是图遍历无向图如果没标记已访问节点DFS会在两个节点之间来回跳形成死循环。修法是在进入一个节点之前就先标记visited递归结束后可以再取消标记如果是回溯需要或者保持标记如果是单纯遍历需要。5.2 结果重复的三种典型原因刷题群里最常见的求助就是“我的结果为啥有重复”。我观察下来原因基本就这三类组合问题忘记用start每次递归都从0开始选导致 [1,2] 和 [2,1] 都会被收到结果里。修复方式递归参数加start下一层从start1开始选。有重复元素但不做排序去重数组里有重复值却没在每层循环里去重导致两个值相同但位置不同元素被当成两种选择。修复方式先排序在每层循环里判断nums[i] nums[i-1]且上一轮位置没被选就跳过。path在存储时未拷贝存进result的是同一个对象的引用后面path一变之前存的“答案”也跟着变。修复方式append时用path[:]。5.3 一个很实用的debug技巧我调试DFS从不靠脑内模拟因为递归深度一深就根本跟不上。我习惯在递归函数的入口和出口各打一行日志打印当前状态和“进入/离开”标记用缩进表示递归层级。def dfs(i, depth0): print( * depth fenter: i{i}, path{path}) if 终止条件: print( * depth freturn: found) return for 选择 in 候选: path.append(选择) dfs(i 1, depth 1) path.pop() print( * depth fexit: i{i})这种打日志的方式能让你把递归的过程“摊平”在眼前一眼就能看到哪个分支没有正常撤销状态、哪个分支提前返回、哪个分支根本没走到。比起在脑子里层层展开效率高太多。我现在调试依然是这个老办法简单但极其好用。5.4 关于递归深度和性能的实话Python的递归深度限制是真实存在的但很多场景其实轮不到它出手。如果你在做深度优先遍历一个几万节点的链表或树递归版本会很快撞到RecursionError这时候就得换显式栈写法或者用sys.setrecursionlimit()提高上限——后者只是治标不治本深度太大照样会爆栈。性能方面DFS的时间复杂度通常是O(分支数^深度)指数级是常态。所以当你在实际项目里遇到DFS跑不动时第一反应不应该是优化DFS本身的常数而是问自己三个问题能不能用动态规划能不能用记忆化能不能先剪枝这三板斧用完了还不行再考虑换算法思路比如BFS、双向搜索、启发式搜索等。我个人在实际项目里比较推荐的做法是先把DFS的裸版本跑通确认逻辑正确然后再逐步加入剪枝和记忆化。直接一上来就写优化版本很容易把状态搞混。先对再优这个顺序写代码永远不吃亏。最后再分享一个小经验如果觉得自己对DFS总是不踏实就去把排列、组合、子集这三道题老老实实手写十遍。每一遍都尝试用不同的实现方式比如递归改成显式栈参数从全局改成传参去重逻辑换成used数组。写完你会发现回溯套路已经刻进肌肉记忆里了。后面遇到岛屿问题、数独、N皇后、括号生成本质上都能往这个框架里套。这套基本功过硬后面的路会好走很多。