DFS 四大核心类别实战题1. 深度优先搜索的思维起点DFS 算法深度优先搜索是算法面试中出现频率最高的一类题型看热搜词里“dfs搜索”“dfs和bfs算法流程图”常年居高不下就知道这玩意儿躲不过去。我面过不少大厂基本每轮coding环节都会碰上一道DFS题有时候是排列组合有时候是矩阵搜索形式不同底层思路完全一样沿着一条路径走到黑撞墙了再回头。很多初学者一上来就背模板、记代码结果题目稍微换一个变体就懵了。原因很简单——DFS不是一个函数而是一种思维范式。只要掌握了“递归三件套”状态定义、递归出口、状态回退再加上“剪枝意识”百分之八十的DFS题都能秒解。我花了大概三周时间把刷过的上百道DFS题归了归类发现其实就四大家族排列组合类、子集枚举类、矩阵搜索类、图遍历与连通块类。这四类覆盖了LeetCode上超过90%的DFS题也基本囊括了大厂面试的常见考点。这篇就把每类的核心思路、经典实战题、以及我踩过的坑一次讲清。2. 第一类排列组合与回溯的暴力美学2.1 全排列最基础的回溯模板排列组合类题目是DFS最经典的应用场景也是我强烈建议初学者第一个吃透的类别。核心思想一句话概括每个位置尝试每种可能用visited数组记录谁已经被用过递归进入下一个位置回溯时撤销选择。以全排列为例LeetCode 46的原题。给定一个不含重复数字的数组返回所有可能的排列。这种题网上随随便便就能搜到一堆解法但我想说的是模板之外的三个关键细节。第一个细节是递归出口的位置。我见过不少初学者把出口写在for循环内部结果要么重复收集结果要么漏掉空集情况。正确做法是进入递归函数的第一件事就判断当前路径长度是否等于原数组长度满足则收集结果并return然后再进入for循环尝试选择。这个顺序一旦颠倒最后一步的完整排列会被漏掉。def permute(nums): res [] path [] visited [False] * len(nums) def backtrack(): if len(path) len(nums): res.append(path[:]) # 一定要拷贝 return for i in range(len(nums)): if visited[i]: continue visited[i] True path.append(nums[i]) backtrack() path.pop() # 撤销选择 visited[i] False # 恢复状态 backtrack() return res第二个关键细节是path[:]这个拷贝操作。如果不拷贝直接res.append(path)收集到的全是同一个列表引用回溯之后路径清空最后res里全是空列表。这个坑我当年踩过面试时也见过不止一个候选人栽在这上面。Python里列表是引用传递append进去的是引用而不是快照理解了这一点就永远不会再错。第三个细节是visited数组和path的同步回退。回溯的本质是“撤销选择”路径和访问标记必须同步恢复一个都不能少。我调试过的不少错误代码就是append了却忘了pop或者visited设了True却忘了设回False导致的结果千奇百怪。2.2 组合总和剪枝的绝佳教材全排列搞定了看一道升级版组合总和LeetCode 39。给定一个无重复元素的数组candidates和一个目标数target找出candidates中所有可以使数字和为target的组合candidates中的数字可以无限制重复被选取。这题比全排列多两个要点。第一允许重复选取同一数字所以递归时index不必1还是从当前index开始继续深挖。第二需要剪枝当当前和已经超过target时继续递归没有意义直接return这就是DFS性能优化的灵魂——减去不需要探索的分支。def combinationSum(candidates, target): res [] path [] candidates.sort() # 排序方便剪枝 def dfs(start, total): if total target: res.append(path[:]) return for i in range(start, len(candidates)): if total candidates[i] target: break # 因为数组升序后面更大直接break path.append(candidates[i]) dfs(i, total candidates[i]) path.pop() dfs(0, 0) return res注意这里用的是break而不是continue前提是数组排过序。一旦当前数字加入后超过target后面的数字更大必然也超所以直接break。这个优化在数组长度很大时效果非常明显。顺带提一句start参数是本类题目防止重复组合的关键。如果递归时不传start而是每次都从头遍历会出现[2,2,3]和[2,3,2]这种元素相同但顺序不同的重复组合这多半不是题目想要的。组合这题还有个变体是LeetCode 40数组里存在重复数字要求结果不能包含重复组合。解法是先排序然后在for循环里跳过同层重复元素——if i start and candidates[i] candidates[i-1]: continue。这个去重逻辑是排列组合类题目最容易混淆的点。我用一句话总结我自己的理解同层去重用的是nums[i] nums[i-1]判断而sincei start保证了只跳过同一层重复的选择不会误伤不同层的合法选择。这个细节面试官非常爱考。2.3 排列组合类实战心得排列组合类的DFS题在面试中属于“必须满分”的送分题但送分不代表不扣分。我自己的面试经验是代码写完只对了还不够面试官一定会追问复杂度。全排列的时间复杂度是O(n!)空间复杂度O(n)递归深度加路径长度组合总和因为剪枝的存在理论上界是O(2^n)但实际表现远好于这个。还有一个实战经验回溯时恢复现场这步最好在递归调用后立刻写而不是等到最后统一处理。原因很简单——以后代码改着改着容易忘记补回退逻辑。递归前做了什么改动递归返回后立刻对称地撤销这个习惯能帮你规避大量隐蔽的bug。提示排列组合类DFS的递归函数参数设计建议遵循“位置参数 状态参数”的模板思路。位置参数如start用来控制可选范围状态参数如visited、total用来记录当前路径的约束条件。当你拿到一个新题不知道怎么写先从这两个维度思考参数怎么设计基本不会跑偏。3. 第二类子集枚举与集合遍历的边界试探3.1 子集问题每个元素的“选或不选”子集类题目和排列组合类很像但考察的角度不同。排列关注的是“顺序”组合和子集关注的是“集合”。LeetCode 78是这类题的地基给定不含重复元素的数组nums返回所有可能的子集。子集的DFS写法有两种主流思路选或不选的递归二叉树以及基于start的for循环枚举。前者理解起来直观后者写起来顺手。我两种都写过的体会是for循环枚举更适合面试因为代码紧凑、不容易漏分支而且和组合类题目的模板能无缝衔接。def subsets(nums): res [] path [] def dfs(index): # 每个状态下当前path都是一个新的子集 res.append(path[:]) for i in range(index, len(nums)): path.append(nums[i]) dfs(i 1) path.pop() dfs(0) return res这段代码和组合总和的模板几乎一模一样唯一的区别是收集时机不同。组合题是等到满足target才收集子集题则是每次进入递归函数时都收集。这个“在任何中间状态都收集”的思路是子集类题目的精髓——因为子集本身就没有长度限制任何前缀都是合法结果。我之前给朋友解释这题时打了个比方遍历集合中的每个元素你可以决定“要”还是“不要”一种决策序列对应一个子集。for循环start模板之所以能覆盖“不要”的情况是因为dfs(i1)天然实现了跳过当前元素的效果。如果想让某个元素不出现我们只需要不选它然后从下一个位置继续枚举即可。3.2 带重复元素的子集排序去重三步法LeetCode 90是子集II数组里有重复元素要求返回不重复的子集组合。这几乎是所有子集题里最容易掉坑的变体也是面试官用来区分“背了模板”和“真懂回溯”的高频考题。解法核心三步排序、同层跳过、正常回溯。和组合总和II的去重逻辑一模一样。我特意把两个题放一起刷的因为它们的去重思想是完全互通的。def subsetsWithDup(nums): res [] path [] nums.sort() # 第一步排序 def dfs(index): res.append(path[:]) for i in range(index, len(nums)): if i index and nums[i] nums[i-1]: continue # 第二步同层去重 path.append(nums[i]) dfs(i 1) path.pop() dfs(0) return res去重逻辑背后的原理值得深挖一下。数组里有两个相同的数字2如果不加任何处理[1,2]这个子集会被构造两次——一次选了第一个2一次选了第二个2。加了i index条件后在同一层循环中如果当前数字和前一个数字相同并且前一个数字还没有被本层选择因为index没变前一个同值数字要么没被选要么选了但已回溯说明当前选择会产生重复结果直接跳过。这个思路是排列组合和子集题目去重的通用钥匙背下来反复用。3.3 子集枚举的进阶排列组合的混合体子集类题目一旦理解透了会发现很多“看起来很高端”的题其实就是它的马甲。LeetCode 401二进制手表、LeetCode 784字母大小写全排列都是子集DFS的变体。784尤其典型给字符串例如a1b2返回所有大小写组合。每个字母有“变大写”和“变小写”两种选择数字则只有一种“选择”——这其实就是带条件判断的子集枚举DFS的模板和subsets几乎一样区别只是在递归时根据字符类型决定分支数量。我刷到这类题时的感受是DFS题型的核心并不是背模板而是识别出“这道题的本质是什么”。一旦你看出它本质上是在枚举每个位置的有限种选择模板自然就浮出水面了。很多同学卡住的原因不是不会写DFS而是不会做从题目到模板的映射。这个映射能力只能靠大量做题练出来没有捷径。4. 第三类二维网格与矩阵中的岛屿穿行4.1 网格DFS的信号看到“连通”或“包围”先想到DFS矩阵类DFS是面试题的另一大阵营。LeetCode 200岛屿数量、130被围绕的区域、79单词搜索每道都是大厂高频题。这类问题的显著特征是给一个二维网格要求统计连通块数量、标记某种状态的区域、或者验证是否存在一条路径关键词是“连通”“相邻”“上下左右”。这类题我习惯把矩阵当作一个隐式的图。每个格子是一个节点每个格子与上下左右四个方向相邻的格子之间有边。DFS遍历时每探索到一个格子就递归深入它的四个邻居直到无路可走。代码层面有两个固定的套路方向数组和边界检查。以岛屿数量为例核心逻辑就一块遍历每个格子遇到没访问过的1就把岛屿计数加一然后从这个格子开始做DFS把这个岛屿上所有的1都“淹没”掉改成0或者标记已访问。这个操作在社区里有个形象的叫法沉没。因为每个1只会被当作某个岛屿的起点一次之后就沉没了不会再重复计数。def numIslands(grid): if not grid: return 0 m, n len(grid), len(grid[0]) # 方向数组上下左右 dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] 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 # 沉没当前格子 for di, dj in dirs: dfs(i di, j dj) count 0 for i in range(m): for j in range(n): if grid[i][j] 1: count 1 dfs(i, j) return count有两个细节值得强调。第一个是方向数组的写法我见过有人写四段独立的if语句不推荐。用元组列表统一管理方向代码精简且不易漏方向。第二个是沉没操作它的实质就是把visited数组融入原矩阵中空间复杂度从O(mn)降到了O(1)。如果面试要求空间优化这个细节是可以讲给面试官听的加分点。4.2 单词搜索路径型DFS与“从哪里来过”LeetCode 79单词搜索是矩阵DFS里最能考察基本功的题目给定一个二维网格和一个单词判断单词是否存在网格中。和岛屿类不同这题不是找连通块而是找路径——网格中的相邻格子需要连成一个和目标单词匹配的序列。路径型DFS比连通块型多一个需求不能重复使用同一个格子。解决方案就是大家耳熟能详的visited标记或者直接在原矩阵上做临时标记。我用Python做题时常用的是一个取巧的写法把当前格子改成特殊值比如#递归返回后再恢复。这样不需要额外开一个二维visited数组简洁且高效。def exist(board, word): m, n len(board), len(board[0]) dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(i, j, k): if board[i][j] ! word[k]: return False if k len(word) - 1: return True # 临时标记 board[i][j] # for di, dj in dirs: ni, nj i di, j dj if 0 ni m and 0 nj n: if dfs(ni, nj, k 1): return True # 恢复标记 board[i][j] word[k] return False for i in range(m): for j in range(n): if dfs(i, j, 0): return True return False这里有个容易被忽视的优化点主循环里可以先做一个字符频次统计如果word中某个字符出现的次数大于网格中总出现次数直接返回False。这个剪枝在极端情况下能把运行时间从几百毫秒压到几毫秒。我实测过word很长但网格字符很少的case效果立竿见影。还有一个实际调bug的心得递归函数里“board[i][j] #”这一步必须在判断base case之后执行。我最初写的时候把标记放在函数第一行结果下一个字符恰好是#虽然题目说只有字母但我这个写法会把原字符盖掉白白浪费了很多调试时间。先把当前格子的匹配判断做完再考虑标记顺序不能乱。4.3 矩阵DFS的复杂度与空间权衡矩阵DFS的时间复杂度通常是O(m×n)因为每个格子在最坏情况下都会被访问一次沉没法保证每个格子最多被访问常数次。单词搜索最坏是O(m×n×3^L)其中L是单词长度因为每步最多有3个方向可以继续去掉回来的那个方向。这个复杂度在面试中最好能脱口而出面试官对复杂度的追问往往比对代码本身的追问更深入。实际比赛中还有一类矩阵DFS考点是“从边界向内部DFS”典型如LeetCode 130被围绕的区域。思路是先找出所有和边界相连的O从这些O做DFS标记为安全区剩下的O就是被包围的全部改成X。我曾经陷入的误区是试图直接在原网格上做DFS判断每个O是否被包围结果逻辑绕来绕去全是bug。后来想通了正难则反从边界的O反向DFS问题立刻简化。这个“反向思维”在矩阵类DFS里非常常用建议专门练一练。5. 第四类图遍历与拓扑排序的前置基础5.1 从“隐式图”到“显式图”邻接表与DFS前面说的排列组合、矩阵题本质上都在图里做DFS只是图的结构是隐式的。真正显式的图遍历题在面试中出现的频率也很高比如“判断有向图是否存在环”“求从某个节点能到达的所有节点”等。这类题需要先构建邻接表再DFS遍历。邻接表的构建本身有个常见的坑图的节点数n可能很大如果用二维矩阵adj[n][n]来存空间是O(n^2)数据量一大就爆内存。正确的做法是字典或者列表形式的邻接表每个节点只存储它能到达的邻居空间O(ne)。这个选型看起来不起眼但在LeetCode的207课程表这类题目中非常关键n可以到2000n^2就是400万勉强能跑但没必要邻接表只需要存几万条边。课程表这题我用一个三色标记法解决每个节点有0未访问、1访问中、2已完成三种状态。DFS进入节点时标记1遍历完所有邻居后标记2。如果在DFS过程中又遇到状态为1的节点说明存在环图没法拓扑排序返回False。def canFinish(numCourses, prerequisites): graph [[] for _ in range(numCourses)] for a, b in prerequisites: graph[b].append(a) # b是a的前置条件 state [0] * numCourses # 0未访问 1访问中 2已完成 def dfs(node): if state[node] 1: return False # 遇到访问中的节点成环 if state[node] 2: return True state[node] 1 for neighbor in graph[node]: if not dfs(neighbor): return False state[node] 2 return True for i in range(numCourses): if not dfs(i): return False return True三色标记法比起朴素的visited数组优势在于它能区分“当前路径上的环”和“已经探索完的路径”。用普通visited数组你只能知道这个节点被访问过无法判断是该return False还是直接跳过。这个细节我在实际面试中被考察过推荐大家彻底理解而不是只背代码。5.2 连通分量计数与DFS的退出时机另一类高频图DFS题是连通分量计数比如LeetCode 323无向图中连通分量的数量。这题的模板和岛屿数量几乎一样区别只是把网格换成了显式图。遍历所有节点每个没访问过的节点做一次DFS把能到的所有点都标记访问连通分量计数加一。这个题的代码不复杂但考察点在于邻接表构建是否熟练以及递归函数里的范围控制是否正确。这道题还有一个经典升级方向用DFS替代并查集。很多讲并查集的文章会用连通分量作为例子但DFS同样能解决而且代码更短。面试时如果你DFS和并查集都会可以主动和面试官讨论两种解法的异同——DFS好处是直观、代码短并查集好处是可以处理动态连接。能聊到这个深度基本就稳了。5.3 图的DFS与全排列的回溯区别说到底图的DFS和排列组合的DFS共享同一个核心机制递归入栈时标记状态递归返回时恢复或固化状态。区别在于排列组合通常需要恢复状态因为我们还要尝试其他排列而图遍历通常不需要恢复因为我们只关心能到达哪些节点不需要尝试走别的路。理解这个区别很重要。我见过有人把岛屿问题的沉没法误以为是回溯操作试图在DFS返回后恢复原网格的值结果陷入死循环。排列组合的“撤销”是为了重新使用这个元素图的“标记”是为了不重复访问两者虽然代码形式上都是改了一个状态标志但代表的语义完全相反。做题时心里要清楚这题需要“恢复现场”还是“固化现场”想清楚了再动手比写完代码再debug要快得多。6. DFS与BFS的选择什么场景无脑选DFS很多人在DFS和BFS之间犹豫其实选择标准非常稳定。简单粗暴的结论求“是否存在一条路径”“是否连通”“所有可能的解”优先DFS求“最短路径”“最少步数”优先BFS求“连通块数量”DFS和BFS都行DFS代码通常更短。这个结论是我在多轮刷题和面试实战中验证过的。DFS和BFS的区别体现在数据结构和空间复杂度上。DFS借助递归栈或显式栈实现空间复杂度等于递归深度最坏情况O(n)BFS借助队列实现空间复杂度是每层节点数的最大值最坏也是O(n)。对于树形结构DFS的空间通常更占优因为树的深度往往远小于一层的节点数。这也是为什么很多树的遍历题默认用DFS的原因——系统栈帮我们省掉了手动管理队列的开销。矩阵类题里的另一个经典选择场景是“计算岛屿最大面积”LeetCode 695。这题DFS写法极短搜索每个1格子时返回1加上四个方向递归的结果之和。这个递归的返回值设计非常巧妙把“计算面积”隐藏在DFS返回值里代码可读性很高。我当初第一次看到这个写法时有种“原来还能这么设计递归函数”的惊艳感。如果你刚开始接触DFS这题值得认真手写三遍以上。7. DFS常见问题与调试技巧实录7.1 递归深度过大导致栈溢出DFS最经典的问题就是递归深度过大时Python会抛出RecursionError。默认递归深度限制是1000层数据量一大就翻车。我在LeetCode上写过一次矩阵DFS矩阵尺寸1000×1000递归深入路径超过1000层直接爆栈。解决方案有三个一是sys.setrecursionlimit(10**6)提高限制二是改用显式栈的迭代DFS三是重新审视递归逻辑看能否用沉没法减少深度。这里必须提醒刷题平台如LeetCode设置递归深度限制是常见的但线上生产环境更多要考虑函数调用的真实开销迭代DFS在绝大多数情况下表现更稳定。如果只是应付面试递归DFS配合setrecursionlimit足够如果要在真实系统里实现图遍历建议直接上迭代写法后面出了bug也更好排查。7.2 回溯时忘了恢复状态的调试方法忘了恢复状态的bug是最隐蔽的因为程序不一定报错只是结果少几个分支或者出现重复。我自己的排查方法是在关键位置打印path和visited。比如全排列问题里递归返回后如果path里莫名其妙少了元素或者visited状态不正确打印当前递归层级的path内容立刻就能看出是哪一步没恢复。另一个更系统的思路把每次“递归前修改”和“递归后恢复”的代码对照写括号对齐检查——先检查是否成对出现再检查是否有缩进错误。我在教朋友刷题时经常让他们做一件事在每段回溯代码的注释里明确写出“这里要恢复什么”和“为什么恢复”。能写清楚这两个问题基本上就不会再犯同类错误。7.3 死循环与无限递归的三类常见诱因无限递归的诱因不外乎三类出口条件写错、状态标记没生效、递归参数没变化。其中“递归参数没变化”是我见过次数最多的低级错误——递归函数期望的是index1结果写成了index第n层和第n-1层参数完全相同永远走不到出口。矩阵类的无限递归则多半是忘了沉没。我刚学DFS时做过一件事写完岛屿数量的DFS不沉没然后每个1的四个方向都会把对方又探索一遍来回震荡最后recursion error。解决方案就是务必在进入DFS后立刻标记先标记再递归禁止先递归再标记。这类错误几乎每个DFS初学者都会经历一次提早踩坑比面试时踩坑好。7.4 DFS常见题目速查表题目类型核心考点关键模板复杂度时间全排列LeetCode 46visited数组回溯排列模板O(n!)组合总和LeetCode 39剪枝start去重组合模板O(2^n)子集LeetCode 78中间状态收集子集模板O(2^n)子集IILeetCode 90排序同层去重子集模板去重O(2^n)单词搜索LeetCode 79临时标记方向数组路径模板O(mn·3^L)岛屿数量LeetCode 200沉没法连通块模板O(mn)课程表LeetCode 207三色标记邻接表图遍历环检测O(ne)8. DFS刷题顺序与面试策略8.1 从高频基础题到变体的四阶段刷题法第一阶段先把全排列、子集、组合总和这三道基础题写到烂熟。第二阶段做矩阵类的岛屿数量、单词搜索、被围绕的区域。第三阶段做图类的课程表、连通分量。第四阶段才开始挑战带复杂剪枝的题目比如N皇后、数独求解。这个顺序特点是从“背模板”逐步过渡到“理解模板”。我自己刷题最大的体会是前三阶段是在积累模式库第四阶段才是在运用和改造模式。跳级刷题容易让思维断档比如单词搜索没刷明白就去刷N皇后很容易被“如何判断冲突”这个业务逻辑带偏反而忽略了DFS本身的框架。8.2 面试中的DFS讲解思路面试里写DFS题有一个我反复验证有效的讲解顺序先讲清楚“这道题本质上在枚举什么”——也就是每个位置有哪些选择再讲“递归函数每个参数的含义是什么”然后讲“递归出口怎么判断”最后讲“需不需要恢复现场及原因”。这个顺序从抽象到具体面试官能跟上你的思路中途发现你有错误也更容易帮你定位。千万别上来就直接写代码。我经历过一次反面案例遇到岛屿数量直接开写边写边解释结果写到方向数组的时候面试官问“DFS和BFS在这题里有什么区别”我被打了个措手不及。后来学乖了先聊思路、聊复杂度、聊选择理由代码只是思维过程的落地自然写得又快又稳。提示面试中如果DFS代码写完运行通过面试官大概率会追问三个问题时间复杂度是多少空间复杂度是多少如果不让用递归你打算怎么写这三个问题一定要提前准备背好标准答案。我的建议是复杂度分析从“每层递归做了多少工作”入手推导迭代DFS用显式栈存“节点状态”两个维度。8.3 从DFS到更高级算法这只是个起点学会了DFS四大家族并不代表算法之路就通关了。DFS是很多高级算法的基石动态规划的“记忆化搜索”本质上就是DFS加缓存数独、N皇后这类搜索题需要DFS配合更复杂的剪枝树的遍历、图的最短路某些场景也都能看到DFS的影子。理解DFS的递归思维之后学那些东西心态上会轻松很多。我自己刷题到后期的一个明显感受是与其追问“这题应该用哪种算法”不如先问“如果我用DFS暴力一点能不能过”。实际上很多题的暴力解就是DFS枚举AC了之后再优化成记忆化搜索或者DP。从这个角度看DFS不是“一种算法”而是“进入算法世界的第一个视角”。9. 写在最后的实操心得这篇文章凝聚了我刷题初期的大量实战经验有几个点再单独强调一次第一DFS模板不要死记要理解状态参数的变化和恢复。第二剪枝是DFS的性能灵魂——组合总和里那个break能省掉一半以上的无用分支矩阵题里的边界检查能省掉一堆异常报错。第三去重逻辑排序同层跳过是“组合组合型”问题的万能钥匙。我个人在实际操作中的一个小习惯是每道DFS题写完把“如果把递归改成迭代怎么写”想清楚。这个练习让我处理过好几次生产环境里的递归爆栈问题。面试准备阶段的你如果时间允许建议也用这个方式复盘——DFS真不是刷一道算一道的题型它是可以举一反三的思维武器练熟了整个搜索家族你都能横着走。
DFS算法实战：四大核心题型与回溯剪枝技巧详解
DFS 四大核心类别实战题1. 深度优先搜索的思维起点DFS 算法深度优先搜索是算法面试中出现频率最高的一类题型看热搜词里“dfs搜索”“dfs和bfs算法流程图”常年居高不下就知道这玩意儿躲不过去。我面过不少大厂基本每轮coding环节都会碰上一道DFS题有时候是排列组合有时候是矩阵搜索形式不同底层思路完全一样沿着一条路径走到黑撞墙了再回头。很多初学者一上来就背模板、记代码结果题目稍微换一个变体就懵了。原因很简单——DFS不是一个函数而是一种思维范式。只要掌握了“递归三件套”状态定义、递归出口、状态回退再加上“剪枝意识”百分之八十的DFS题都能秒解。我花了大概三周时间把刷过的上百道DFS题归了归类发现其实就四大家族排列组合类、子集枚举类、矩阵搜索类、图遍历与连通块类。这四类覆盖了LeetCode上超过90%的DFS题也基本囊括了大厂面试的常见考点。这篇就把每类的核心思路、经典实战题、以及我踩过的坑一次讲清。2. 第一类排列组合与回溯的暴力美学2.1 全排列最基础的回溯模板排列组合类题目是DFS最经典的应用场景也是我强烈建议初学者第一个吃透的类别。核心思想一句话概括每个位置尝试每种可能用visited数组记录谁已经被用过递归进入下一个位置回溯时撤销选择。以全排列为例LeetCode 46的原题。给定一个不含重复数字的数组返回所有可能的排列。这种题网上随随便便就能搜到一堆解法但我想说的是模板之外的三个关键细节。第一个细节是递归出口的位置。我见过不少初学者把出口写在for循环内部结果要么重复收集结果要么漏掉空集情况。正确做法是进入递归函数的第一件事就判断当前路径长度是否等于原数组长度满足则收集结果并return然后再进入for循环尝试选择。这个顺序一旦颠倒最后一步的完整排列会被漏掉。def permute(nums): res [] path [] visited [False] * len(nums) def backtrack(): if len(path) len(nums): res.append(path[:]) # 一定要拷贝 return for i in range(len(nums)): if visited[i]: continue visited[i] True path.append(nums[i]) backtrack() path.pop() # 撤销选择 visited[i] False # 恢复状态 backtrack() return res第二个关键细节是path[:]这个拷贝操作。如果不拷贝直接res.append(path)收集到的全是同一个列表引用回溯之后路径清空最后res里全是空列表。这个坑我当年踩过面试时也见过不止一个候选人栽在这上面。Python里列表是引用传递append进去的是引用而不是快照理解了这一点就永远不会再错。第三个细节是visited数组和path的同步回退。回溯的本质是“撤销选择”路径和访问标记必须同步恢复一个都不能少。我调试过的不少错误代码就是append了却忘了pop或者visited设了True却忘了设回False导致的结果千奇百怪。2.2 组合总和剪枝的绝佳教材全排列搞定了看一道升级版组合总和LeetCode 39。给定一个无重复元素的数组candidates和一个目标数target找出candidates中所有可以使数字和为target的组合candidates中的数字可以无限制重复被选取。这题比全排列多两个要点。第一允许重复选取同一数字所以递归时index不必1还是从当前index开始继续深挖。第二需要剪枝当当前和已经超过target时继续递归没有意义直接return这就是DFS性能优化的灵魂——减去不需要探索的分支。def combinationSum(candidates, target): res [] path [] candidates.sort() # 排序方便剪枝 def dfs(start, total): if total target: res.append(path[:]) return for i in range(start, len(candidates)): if total candidates[i] target: break # 因为数组升序后面更大直接break path.append(candidates[i]) dfs(i, total candidates[i]) path.pop() dfs(0, 0) return res注意这里用的是break而不是continue前提是数组排过序。一旦当前数字加入后超过target后面的数字更大必然也超所以直接break。这个优化在数组长度很大时效果非常明显。顺带提一句start参数是本类题目防止重复组合的关键。如果递归时不传start而是每次都从头遍历会出现[2,2,3]和[2,3,2]这种元素相同但顺序不同的重复组合这多半不是题目想要的。组合这题还有个变体是LeetCode 40数组里存在重复数字要求结果不能包含重复组合。解法是先排序然后在for循环里跳过同层重复元素——if i start and candidates[i] candidates[i-1]: continue。这个去重逻辑是排列组合类题目最容易混淆的点。我用一句话总结我自己的理解同层去重用的是nums[i] nums[i-1]判断而sincei start保证了只跳过同一层重复的选择不会误伤不同层的合法选择。这个细节面试官非常爱考。2.3 排列组合类实战心得排列组合类的DFS题在面试中属于“必须满分”的送分题但送分不代表不扣分。我自己的面试经验是代码写完只对了还不够面试官一定会追问复杂度。全排列的时间复杂度是O(n!)空间复杂度O(n)递归深度加路径长度组合总和因为剪枝的存在理论上界是O(2^n)但实际表现远好于这个。还有一个实战经验回溯时恢复现场这步最好在递归调用后立刻写而不是等到最后统一处理。原因很简单——以后代码改着改着容易忘记补回退逻辑。递归前做了什么改动递归返回后立刻对称地撤销这个习惯能帮你规避大量隐蔽的bug。提示排列组合类DFS的递归函数参数设计建议遵循“位置参数 状态参数”的模板思路。位置参数如start用来控制可选范围状态参数如visited、total用来记录当前路径的约束条件。当你拿到一个新题不知道怎么写先从这两个维度思考参数怎么设计基本不会跑偏。3. 第二类子集枚举与集合遍历的边界试探3.1 子集问题每个元素的“选或不选”子集类题目和排列组合类很像但考察的角度不同。排列关注的是“顺序”组合和子集关注的是“集合”。LeetCode 78是这类题的地基给定不含重复元素的数组nums返回所有可能的子集。子集的DFS写法有两种主流思路选或不选的递归二叉树以及基于start的for循环枚举。前者理解起来直观后者写起来顺手。我两种都写过的体会是for循环枚举更适合面试因为代码紧凑、不容易漏分支而且和组合类题目的模板能无缝衔接。def subsets(nums): res [] path [] def dfs(index): # 每个状态下当前path都是一个新的子集 res.append(path[:]) for i in range(index, len(nums)): path.append(nums[i]) dfs(i 1) path.pop() dfs(0) return res这段代码和组合总和的模板几乎一模一样唯一的区别是收集时机不同。组合题是等到满足target才收集子集题则是每次进入递归函数时都收集。这个“在任何中间状态都收集”的思路是子集类题目的精髓——因为子集本身就没有长度限制任何前缀都是合法结果。我之前给朋友解释这题时打了个比方遍历集合中的每个元素你可以决定“要”还是“不要”一种决策序列对应一个子集。for循环start模板之所以能覆盖“不要”的情况是因为dfs(i1)天然实现了跳过当前元素的效果。如果想让某个元素不出现我们只需要不选它然后从下一个位置继续枚举即可。3.2 带重复元素的子集排序去重三步法LeetCode 90是子集II数组里有重复元素要求返回不重复的子集组合。这几乎是所有子集题里最容易掉坑的变体也是面试官用来区分“背了模板”和“真懂回溯”的高频考题。解法核心三步排序、同层跳过、正常回溯。和组合总和II的去重逻辑一模一样。我特意把两个题放一起刷的因为它们的去重思想是完全互通的。def subsetsWithDup(nums): res [] path [] nums.sort() # 第一步排序 def dfs(index): res.append(path[:]) for i in range(index, len(nums)): if i index and nums[i] nums[i-1]: continue # 第二步同层去重 path.append(nums[i]) dfs(i 1) path.pop() dfs(0) return res去重逻辑背后的原理值得深挖一下。数组里有两个相同的数字2如果不加任何处理[1,2]这个子集会被构造两次——一次选了第一个2一次选了第二个2。加了i index条件后在同一层循环中如果当前数字和前一个数字相同并且前一个数字还没有被本层选择因为index没变前一个同值数字要么没被选要么选了但已回溯说明当前选择会产生重复结果直接跳过。这个思路是排列组合和子集题目去重的通用钥匙背下来反复用。3.3 子集枚举的进阶排列组合的混合体子集类题目一旦理解透了会发现很多“看起来很高端”的题其实就是它的马甲。LeetCode 401二进制手表、LeetCode 784字母大小写全排列都是子集DFS的变体。784尤其典型给字符串例如a1b2返回所有大小写组合。每个字母有“变大写”和“变小写”两种选择数字则只有一种“选择”——这其实就是带条件判断的子集枚举DFS的模板和subsets几乎一样区别只是在递归时根据字符类型决定分支数量。我刷到这类题时的感受是DFS题型的核心并不是背模板而是识别出“这道题的本质是什么”。一旦你看出它本质上是在枚举每个位置的有限种选择模板自然就浮出水面了。很多同学卡住的原因不是不会写DFS而是不会做从题目到模板的映射。这个映射能力只能靠大量做题练出来没有捷径。4. 第三类二维网格与矩阵中的岛屿穿行4.1 网格DFS的信号看到“连通”或“包围”先想到DFS矩阵类DFS是面试题的另一大阵营。LeetCode 200岛屿数量、130被围绕的区域、79单词搜索每道都是大厂高频题。这类问题的显著特征是给一个二维网格要求统计连通块数量、标记某种状态的区域、或者验证是否存在一条路径关键词是“连通”“相邻”“上下左右”。这类题我习惯把矩阵当作一个隐式的图。每个格子是一个节点每个格子与上下左右四个方向相邻的格子之间有边。DFS遍历时每探索到一个格子就递归深入它的四个邻居直到无路可走。代码层面有两个固定的套路方向数组和边界检查。以岛屿数量为例核心逻辑就一块遍历每个格子遇到没访问过的1就把岛屿计数加一然后从这个格子开始做DFS把这个岛屿上所有的1都“淹没”掉改成0或者标记已访问。这个操作在社区里有个形象的叫法沉没。因为每个1只会被当作某个岛屿的起点一次之后就沉没了不会再重复计数。def numIslands(grid): if not grid: return 0 m, n len(grid), len(grid[0]) # 方向数组上下左右 dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] 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 # 沉没当前格子 for di, dj in dirs: dfs(i di, j dj) count 0 for i in range(m): for j in range(n): if grid[i][j] 1: count 1 dfs(i, j) return count有两个细节值得强调。第一个是方向数组的写法我见过有人写四段独立的if语句不推荐。用元组列表统一管理方向代码精简且不易漏方向。第二个是沉没操作它的实质就是把visited数组融入原矩阵中空间复杂度从O(mn)降到了O(1)。如果面试要求空间优化这个细节是可以讲给面试官听的加分点。4.2 单词搜索路径型DFS与“从哪里来过”LeetCode 79单词搜索是矩阵DFS里最能考察基本功的题目给定一个二维网格和一个单词判断单词是否存在网格中。和岛屿类不同这题不是找连通块而是找路径——网格中的相邻格子需要连成一个和目标单词匹配的序列。路径型DFS比连通块型多一个需求不能重复使用同一个格子。解决方案就是大家耳熟能详的visited标记或者直接在原矩阵上做临时标记。我用Python做题时常用的是一个取巧的写法把当前格子改成特殊值比如#递归返回后再恢复。这样不需要额外开一个二维visited数组简洁且高效。def exist(board, word): m, n len(board), len(board[0]) dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(i, j, k): if board[i][j] ! word[k]: return False if k len(word) - 1: return True # 临时标记 board[i][j] # for di, dj in dirs: ni, nj i di, j dj if 0 ni m and 0 nj n: if dfs(ni, nj, k 1): return True # 恢复标记 board[i][j] word[k] return False for i in range(m): for j in range(n): if dfs(i, j, 0): return True return False这里有个容易被忽视的优化点主循环里可以先做一个字符频次统计如果word中某个字符出现的次数大于网格中总出现次数直接返回False。这个剪枝在极端情况下能把运行时间从几百毫秒压到几毫秒。我实测过word很长但网格字符很少的case效果立竿见影。还有一个实际调bug的心得递归函数里“board[i][j] #”这一步必须在判断base case之后执行。我最初写的时候把标记放在函数第一行结果下一个字符恰好是#虽然题目说只有字母但我这个写法会把原字符盖掉白白浪费了很多调试时间。先把当前格子的匹配判断做完再考虑标记顺序不能乱。4.3 矩阵DFS的复杂度与空间权衡矩阵DFS的时间复杂度通常是O(m×n)因为每个格子在最坏情况下都会被访问一次沉没法保证每个格子最多被访问常数次。单词搜索最坏是O(m×n×3^L)其中L是单词长度因为每步最多有3个方向可以继续去掉回来的那个方向。这个复杂度在面试中最好能脱口而出面试官对复杂度的追问往往比对代码本身的追问更深入。实际比赛中还有一类矩阵DFS考点是“从边界向内部DFS”典型如LeetCode 130被围绕的区域。思路是先找出所有和边界相连的O从这些O做DFS标记为安全区剩下的O就是被包围的全部改成X。我曾经陷入的误区是试图直接在原网格上做DFS判断每个O是否被包围结果逻辑绕来绕去全是bug。后来想通了正难则反从边界的O反向DFS问题立刻简化。这个“反向思维”在矩阵类DFS里非常常用建议专门练一练。5. 第四类图遍历与拓扑排序的前置基础5.1 从“隐式图”到“显式图”邻接表与DFS前面说的排列组合、矩阵题本质上都在图里做DFS只是图的结构是隐式的。真正显式的图遍历题在面试中出现的频率也很高比如“判断有向图是否存在环”“求从某个节点能到达的所有节点”等。这类题需要先构建邻接表再DFS遍历。邻接表的构建本身有个常见的坑图的节点数n可能很大如果用二维矩阵adj[n][n]来存空间是O(n^2)数据量一大就爆内存。正确的做法是字典或者列表形式的邻接表每个节点只存储它能到达的邻居空间O(ne)。这个选型看起来不起眼但在LeetCode的207课程表这类题目中非常关键n可以到2000n^2就是400万勉强能跑但没必要邻接表只需要存几万条边。课程表这题我用一个三色标记法解决每个节点有0未访问、1访问中、2已完成三种状态。DFS进入节点时标记1遍历完所有邻居后标记2。如果在DFS过程中又遇到状态为1的节点说明存在环图没法拓扑排序返回False。def canFinish(numCourses, prerequisites): graph [[] for _ in range(numCourses)] for a, b in prerequisites: graph[b].append(a) # b是a的前置条件 state [0] * numCourses # 0未访问 1访问中 2已完成 def dfs(node): if state[node] 1: return False # 遇到访问中的节点成环 if state[node] 2: return True state[node] 1 for neighbor in graph[node]: if not dfs(neighbor): return False state[node] 2 return True for i in range(numCourses): if not dfs(i): return False return True三色标记法比起朴素的visited数组优势在于它能区分“当前路径上的环”和“已经探索完的路径”。用普通visited数组你只能知道这个节点被访问过无法判断是该return False还是直接跳过。这个细节我在实际面试中被考察过推荐大家彻底理解而不是只背代码。5.2 连通分量计数与DFS的退出时机另一类高频图DFS题是连通分量计数比如LeetCode 323无向图中连通分量的数量。这题的模板和岛屿数量几乎一样区别只是把网格换成了显式图。遍历所有节点每个没访问过的节点做一次DFS把能到的所有点都标记访问连通分量计数加一。这个题的代码不复杂但考察点在于邻接表构建是否熟练以及递归函数里的范围控制是否正确。这道题还有一个经典升级方向用DFS替代并查集。很多讲并查集的文章会用连通分量作为例子但DFS同样能解决而且代码更短。面试时如果你DFS和并查集都会可以主动和面试官讨论两种解法的异同——DFS好处是直观、代码短并查集好处是可以处理动态连接。能聊到这个深度基本就稳了。5.3 图的DFS与全排列的回溯区别说到底图的DFS和排列组合的DFS共享同一个核心机制递归入栈时标记状态递归返回时恢复或固化状态。区别在于排列组合通常需要恢复状态因为我们还要尝试其他排列而图遍历通常不需要恢复因为我们只关心能到达哪些节点不需要尝试走别的路。理解这个区别很重要。我见过有人把岛屿问题的沉没法误以为是回溯操作试图在DFS返回后恢复原网格的值结果陷入死循环。排列组合的“撤销”是为了重新使用这个元素图的“标记”是为了不重复访问两者虽然代码形式上都是改了一个状态标志但代表的语义完全相反。做题时心里要清楚这题需要“恢复现场”还是“固化现场”想清楚了再动手比写完代码再debug要快得多。6. DFS与BFS的选择什么场景无脑选DFS很多人在DFS和BFS之间犹豫其实选择标准非常稳定。简单粗暴的结论求“是否存在一条路径”“是否连通”“所有可能的解”优先DFS求“最短路径”“最少步数”优先BFS求“连通块数量”DFS和BFS都行DFS代码通常更短。这个结论是我在多轮刷题和面试实战中验证过的。DFS和BFS的区别体现在数据结构和空间复杂度上。DFS借助递归栈或显式栈实现空间复杂度等于递归深度最坏情况O(n)BFS借助队列实现空间复杂度是每层节点数的最大值最坏也是O(n)。对于树形结构DFS的空间通常更占优因为树的深度往往远小于一层的节点数。这也是为什么很多树的遍历题默认用DFS的原因——系统栈帮我们省掉了手动管理队列的开销。矩阵类题里的另一个经典选择场景是“计算岛屿最大面积”LeetCode 695。这题DFS写法极短搜索每个1格子时返回1加上四个方向递归的结果之和。这个递归的返回值设计非常巧妙把“计算面积”隐藏在DFS返回值里代码可读性很高。我当初第一次看到这个写法时有种“原来还能这么设计递归函数”的惊艳感。如果你刚开始接触DFS这题值得认真手写三遍以上。7. DFS常见问题与调试技巧实录7.1 递归深度过大导致栈溢出DFS最经典的问题就是递归深度过大时Python会抛出RecursionError。默认递归深度限制是1000层数据量一大就翻车。我在LeetCode上写过一次矩阵DFS矩阵尺寸1000×1000递归深入路径超过1000层直接爆栈。解决方案有三个一是sys.setrecursionlimit(10**6)提高限制二是改用显式栈的迭代DFS三是重新审视递归逻辑看能否用沉没法减少深度。这里必须提醒刷题平台如LeetCode设置递归深度限制是常见的但线上生产环境更多要考虑函数调用的真实开销迭代DFS在绝大多数情况下表现更稳定。如果只是应付面试递归DFS配合setrecursionlimit足够如果要在真实系统里实现图遍历建议直接上迭代写法后面出了bug也更好排查。7.2 回溯时忘了恢复状态的调试方法忘了恢复状态的bug是最隐蔽的因为程序不一定报错只是结果少几个分支或者出现重复。我自己的排查方法是在关键位置打印path和visited。比如全排列问题里递归返回后如果path里莫名其妙少了元素或者visited状态不正确打印当前递归层级的path内容立刻就能看出是哪一步没恢复。另一个更系统的思路把每次“递归前修改”和“递归后恢复”的代码对照写括号对齐检查——先检查是否成对出现再检查是否有缩进错误。我在教朋友刷题时经常让他们做一件事在每段回溯代码的注释里明确写出“这里要恢复什么”和“为什么恢复”。能写清楚这两个问题基本上就不会再犯同类错误。7.3 死循环与无限递归的三类常见诱因无限递归的诱因不外乎三类出口条件写错、状态标记没生效、递归参数没变化。其中“递归参数没变化”是我见过次数最多的低级错误——递归函数期望的是index1结果写成了index第n层和第n-1层参数完全相同永远走不到出口。矩阵类的无限递归则多半是忘了沉没。我刚学DFS时做过一件事写完岛屿数量的DFS不沉没然后每个1的四个方向都会把对方又探索一遍来回震荡最后recursion error。解决方案就是务必在进入DFS后立刻标记先标记再递归禁止先递归再标记。这类错误几乎每个DFS初学者都会经历一次提早踩坑比面试时踩坑好。7.4 DFS常见题目速查表题目类型核心考点关键模板复杂度时间全排列LeetCode 46visited数组回溯排列模板O(n!)组合总和LeetCode 39剪枝start去重组合模板O(2^n)子集LeetCode 78中间状态收集子集模板O(2^n)子集IILeetCode 90排序同层去重子集模板去重O(2^n)单词搜索LeetCode 79临时标记方向数组路径模板O(mn·3^L)岛屿数量LeetCode 200沉没法连通块模板O(mn)课程表LeetCode 207三色标记邻接表图遍历环检测O(ne)8. DFS刷题顺序与面试策略8.1 从高频基础题到变体的四阶段刷题法第一阶段先把全排列、子集、组合总和这三道基础题写到烂熟。第二阶段做矩阵类的岛屿数量、单词搜索、被围绕的区域。第三阶段做图类的课程表、连通分量。第四阶段才开始挑战带复杂剪枝的题目比如N皇后、数独求解。这个顺序特点是从“背模板”逐步过渡到“理解模板”。我自己刷题最大的体会是前三阶段是在积累模式库第四阶段才是在运用和改造模式。跳级刷题容易让思维断档比如单词搜索没刷明白就去刷N皇后很容易被“如何判断冲突”这个业务逻辑带偏反而忽略了DFS本身的框架。8.2 面试中的DFS讲解思路面试里写DFS题有一个我反复验证有效的讲解顺序先讲清楚“这道题本质上在枚举什么”——也就是每个位置有哪些选择再讲“递归函数每个参数的含义是什么”然后讲“递归出口怎么判断”最后讲“需不需要恢复现场及原因”。这个顺序从抽象到具体面试官能跟上你的思路中途发现你有错误也更容易帮你定位。千万别上来就直接写代码。我经历过一次反面案例遇到岛屿数量直接开写边写边解释结果写到方向数组的时候面试官问“DFS和BFS在这题里有什么区别”我被打了个措手不及。后来学乖了先聊思路、聊复杂度、聊选择理由代码只是思维过程的落地自然写得又快又稳。提示面试中如果DFS代码写完运行通过面试官大概率会追问三个问题时间复杂度是多少空间复杂度是多少如果不让用递归你打算怎么写这三个问题一定要提前准备背好标准答案。我的建议是复杂度分析从“每层递归做了多少工作”入手推导迭代DFS用显式栈存“节点状态”两个维度。8.3 从DFS到更高级算法这只是个起点学会了DFS四大家族并不代表算法之路就通关了。DFS是很多高级算法的基石动态规划的“记忆化搜索”本质上就是DFS加缓存数独、N皇后这类搜索题需要DFS配合更复杂的剪枝树的遍历、图的最短路某些场景也都能看到DFS的影子。理解DFS的递归思维之后学那些东西心态上会轻松很多。我自己刷题到后期的一个明显感受是与其追问“这题应该用哪种算法”不如先问“如果我用DFS暴力一点能不能过”。实际上很多题的暴力解就是DFS枚举AC了之后再优化成记忆化搜索或者DP。从这个角度看DFS不是“一种算法”而是“进入算法世界的第一个视角”。9. 写在最后的实操心得这篇文章凝聚了我刷题初期的大量实战经验有几个点再单独强调一次第一DFS模板不要死记要理解状态参数的变化和恢复。第二剪枝是DFS的性能灵魂——组合总和里那个break能省掉一半以上的无用分支矩阵题里的边界检查能省掉一堆异常报错。第三去重逻辑排序同层跳过是“组合组合型”问题的万能钥匙。我个人在实际操作中的一个小习惯是每道DFS题写完把“如果把递归改成迭代怎么写”想清楚。这个练习让我处理过好几次生产环境里的递归爆栈问题。面试准备阶段的你如果时间允许建议也用这个方式复盘——DFS真不是刷一道算一道的题型它是可以举一反三的思维武器练熟了整个搜索家族你都能横着走。
