企业官网建设流程全解析

1. 从一道递归题说起：DFS到底在解决什么问题

今天是我算法打卡的第44天，主角是DFS（Depth First Search，深度优先搜索）。如果你正在刷题或者准备面试，迟早会撞上这个名字。它听起来像某个高深的数据结构，实际上它只是“一条路走到底，走不通就回头换一条”的搜索策略。

很多人第一次接触DFS是在二叉树遍历，先序遍历就是典型的DFS：从根节点出发，一路往左走到最深处，再逐层往回退，每退一步看看右边有没有没走的分支，有就钻进去继续走到底。这个“走到底再回头”的动作，就是深度优先的核心。和它在同一个家族的还有BFS（广度优先搜索），BFS是先扫完离起点最近的一层再往深处走，像是水波一圈圈扩散。两个都是图论和树结构里的基础算法，但DFS因为实现简单、思路契合递归，几乎是所有初学者最早掌握的搜索工具。

那DFS能做什么？三个最典型的场景：一是遍历，比如打印一棵树的全部节点、统计图里能到达的所有节点；二是搜索路径，比如在迷宫或棋盘上找一条从起点到终点的通路；三是在解空间里寻找满足条件的组合、排列、子集，比如从一组数字里挑出所有和为某个值的组合。第二个和第三个场景我练得最多，因为它们直接对应了大量LeetCode中等题和竞赛里高频出现的题目类型。

这篇内容适合谁？如果你刚开始学递归、刚接触图和树，或者已经刷了一些题但一看到题目里有“枚举所有可能”“找全部方案”就觉得心里没底，那这篇笔记对你会有帮助。我会把DFS的底层逻辑、手写递归的实现细节、常见的踩坑点以及剪枝优化一次讲清，并且用具体的题目案例做推演。不是为了背模板，而是搞清楚它为什么这么写、每个参数为什么在这里出现、状态为什么要在返回前恢复。

我自己的体会是，DFS不是一个需要背八遍的“套路”，它是一种需要亲手多画几轮递归展开图的思维方式。第44天这个节点，我算是把DFS从“会写模板”推进到了“能根据不同题目调整状态定义和剪枝策略”的阶段，这篇就是把这一路摸出来的经验沉淀下来。

2. 理解DFS背后的递归模型

2.1 把问题拆成一棵决策树

要弄懂DFS，最好把它映射到一棵“决策树”上。树上的每个节点代表一个“当前局面”，节点往下伸出的每条边代表“做一次选择之后形成的新局面”。DFS要做的事情就是从根节点（初始状态）出发，沿着一条分支反复往下走，直到走到叶子节点——也就是到达了边界条件或找到了完整答案——再返回上一个分叉点，换另一条边继续走。

举个例子，假设要在集合{1, 2, 3}中枚举所有子集。根节点是“空集合，还没决定任何元素选不选”。对数字1，有两种选择：选、不选。从根节点分出两个子节点。对第二个数字2，在每一个子节点上又各分出两种选择，节点数翻倍。到了第三个数字3，整棵树展开成8个叶子节点，对应8个子集。DFS就是沿着这棵树从根一路走到底，每次走到叶子就记录一个结果，然后回溯回上一层去寻找另一条分支。

这里有一个关键认知：DFS和整棵决策树的形状是绑定的。树有多少层、每层有多少个分支，决定了递归的深度和每一层循环或选择的次数。所以写DFS的第一步不是急着敲代码，而是先在纸上明确三个问题：每一步在做什么选择、选择范围是什么、什么时候算走到头。这三个问题回答了，递归函数的长相基本就出来了。

我用一道具体题目来说明。经典的全排列问题：给定数组[1, 2, 3]，输出所有排列。决策树的根节点是“当前排列为空”，第一层决定第一个位置放哪个数，有三个选择；第二层决定第二个位置放哪个数，从剩余数字里选两个之一；第三层只剩最后一个数，叶子节点就是完整排列。树的深度等于数组长度，每层的分支数递减。这个过程用递归写，就是“当前层遍历所有可以选的数字，选完一个就递归进入下一层，等递归返回后把状态还原”。

2.2 递归深度与系统调用栈的关系

DFS最常见的实现方式是递归，递归之所以能自动实现“深入再返回”，依赖的是系统调用栈。每次调用函数，计算机会把当前函数的所有局部变量、参数、返回地址压入栈中，等被调用的函数返回后，再从栈顶恢复之前的现场继续执行。这正好和DFS“往下走一步”和“回溯上一步”的动作一一对应。

所以“递归深度”本质上就是“调用栈最大能压多深”。默认情况下，Python的递归深度限制是1000层左右（不同版本略有差异），Java的栈空间取决于JVM配置，C++在Linux下的栈空间通常是8MB。如果题目需要DFS搜索的层数极深，比如在网格里逐格标记连通区域，递归深度可能达到网格的行数加列数级别，这时候就要小心栈溢出。

我之前遇到过一个特别典型的场景：在500x500的网格上做“岛屿数量”类题目的DFS，每个格子向四个方向递归，虽然每一层只是换了一个格子，递归深度在最坏情况下可能达到250000层，远超默认的递归上限。直接用递归实现在Python里会直接报RecursionError。这时候有两种处理思路：一是用sys.setrecursionlimit把上限调高，调到1000000，但调太高会带来真实的内存风险；二是改用显式栈实现，也就是把系统帮我们压栈的过程自己用list手动模拟，进栈出栈完全可控。两者我都试过，显式栈在极端情况下更稳，但它失去了递归那种“天然回溯”的简洁性，代码会啰嗦不少，所以我的建议是：平时练习和笔试用递归，面试或者需要极致稳定的大规模网格处理再考虑显式栈。

2.3 DFS与BFS的选型对比

既然DFS和BFS都能用来遍历和搜路径，那就绕不开一个常见困惑：什么时候该用DFS，什么时候该用BFS？

我的判断标准很简单：如果题目问的是“有没有解”“有多少解”“所有解分别是什么”，优先考虑DFS，因为它会顺着一条分支一直探索到终点，用递归写最自然，而且枚举所有方案本来就是它的强项。如果题目问的是“从起点到终点的最短路径是几步”“最近公共祖先在哪一层”，这种情况需要按层次推进，BFS更合适，因为BFS天然带有“逐层扩展”的性质，第一次到达目标节点时走的路径一定是最短的。

举一个迷宫题的例子。给定一个二维迷宫，问“是否存在一条从左上角到右下角的通路”，DFS和BFS都能做，DFS更简单：从一个格子往四个方向递归，能走就继续走，走不通就回退。但如果问的是“最少要走多少步”，DFS就麻烦了——你得搜索所有可能路径，记录每条路径的长度，最后取最小值；而BFS第一次扩展到终点时，路径长度就是最短步数。这两种场景我在刷题过程中反复遇到，每次都觉得如果一开始判断错了方向，代码量差距可能就是几十行。

所以不要只看“DFS名字听起来熟悉”就无脑选它，先看看题面说的是“找出全部方案”还是“找最短路径”，这一步判断对了，后面的实现会顺畅很多。

3. 手写DFS的实现要点：递归函数、访问标记与回溯

3.1 模板框架与三个必备参数

DFS递归函数的写法没有一个绝对模板，但大多数题目的实现都会围绕几个固定要素转。先看一个我在刷题过程中整理出来的相对通用的框架：

def dfs(level, path, used): # 1. 终止条件：到底了，记录答案 if level == target: result.append(path[:]) return # 2. 遍历当前层可选的选项 for option in candidates: if used[option] is True: continue # 3. 做出选择：标记 + 加入路径 used[option] = True path.append(option) # 4. 进入下一层递归 dfs(level + 1, path, used) # 5. 撤销选择：恢复标记 + 弹出路径 path.pop() used[option] = False

这里有三个参数几乎是必备的：level表示当前递归到第几层（也可以理解成“已经做出了多少个选择”）；path用来保存当前已经选出的路径或部分答案；used表示哪些元素已经被用过，在排列类题目里特别重要，避免同一个数被选两次。

很多初学者第一次写DFS时会漏掉第5步——撤销选择。这两行代码是整个回溯的灵魂。因为递归进入下一层之后，假如不把当前元素“放回去”，回到上一层尝试其他分支时，used标记仍然是带进来的旧状态，导致搜索空间被污染，要么漏掉正确答案，要么产生错误结果。我盯着调试器看自己代码的时候，至少有三次卡在“为什么这个分支少了一个候选数字”的问题上，最后都是撤销没写全。

需要注意，有些题目里的“撤销”不只是恢复布尔标记。比如排列题目里，path列表要pop掉末尾元素；组合求和题里，sum值要在递归返回后减掉当前数字；棋盘题里，放置过的皇后要移掉。凡是“选择”产生了副作用，都必须要在递归返回之后做镜像的“反操作”，才能保证兄弟分支之间互不干扰。这叫回溯的“对称性”，它是我判断DFS代码写没写对的一个重要直觉：所有在递归前改动的状态，递归后一定要还原。

3.2 状态标记的两种用法：条带标记与路径标记

访问标记used有两种常见含义，很多人没区分清楚，导致同一个题换了情境就懵。第一种是“全局不可复用”标记：在一个搜索过程里，某个节点或元素一旦被访问过就再也不允许其他分支使用它。典型场景是图的遍历和排列组合去重。所有递归分支共享同一个used数组，回溯时要恢复，原因正是为了让另一条分支能重新选它。第二种是“本次路径专属”标记：记录从根到当前节点这条路径上已经走过哪些点，只对当前路径有效。典型场景是欧拉路径、Hamiltonian路径类问题，以及部分棋盘搜索题。

这两种标记在代码层面往往长得一模一样，唯一的不同在于对“恢复时机”的要求。前者如果忘记恢复，后续其他分支全都会受波及，属于灾难性bug；后者如果不做恢复，那么同一条路径上确实不该重复走同一点，但换了新路径之后旧路径上的信息就不该再保留。判断到底是哪一种，可以在写代码前问自己一个问题：空格子访问过后，其他路径是否允许再次进入？如果答案是“允许”，就必须恢复。

我踩过一个非常典型的坑：岛屿数量题目里，我最初用DFS标记一个格子已经被访问，用的是局部二维数组visited，每个递归分支都传一个新的副本，想在并行分支间保持隔离，结果内存爆炸，性能一塌糊涂。后来改成在原数组上把已经访问过的“1”改成“0”（就地标记法），每一次递归返回后并不恢复，因为这道题的语义是“这个格子已经纳入当前连通块，其他搜索不需要再碰它”，反而又简单又快。这让我深刻体会到：状态标记不等于“有标记就一定有回溯”，取决于题意是“走过不再走”还是“分支之间要隔离”。

3.3 剪枝：哪些分支可以提前放弃

DFS在没有剪枝的情况下，往往会在庞大的解空间里白白兜圈子。剪枝的本质是提前判断某条分支绝不可能产生有效答案，然后直接不走。这听起来很美好，但初学者最需要想清楚的是“为什么敢剪”——因为剪枝一旦误判，正确解会被直接丢干净。

常见的剪枝策略有几类。第一类叫可行性剪枝：已经明确当前路径不管怎么走下去都无法满足题目条件。比如组合总和题目中，目标sum是8，当前累加和已经超过8，而数组元素全是正整数，继续加只会更大，所以可以直接终止这条分支。这个“全是正整数”的前提就是剪枝的依据，数字一旦包含负数，这个剪枝就不成立了。

第二类叫最优性剪枝：搜索目标是最小值或最大值，如果当前已经花费的代价已经不小于目前记录的最好答案，那继续往下走也不可能更优，直接跳过。这个策略在最短路径、拼图类问题上非常有用。

第三类叫排序去重剪枝：先对候选元素排序，在for循环中如果发现当前元素和前一个元素相等，且前一个元素没有在当前路径中被使用，那么这一轮选择会生成重复结果，直接跳过。这个技巧在处理“数组中存在重复元素，枚举所有不重复组合”的题目时几乎是标配。

我在写组合总和II这个经典题时对排序去重印象极深。输入是[1, 1, 2, 3]，目标值是5，如果不做去重剪枝，会得到[1, 2, 2]？不对，这里数组里只有一个2，举例不严谨——应该说会生成两个[1, 3]这样的重复组合，因为两个“1”地位相同，先选第一个1还是先选第二个1会被DFS视为两条路径。剪枝条件“当前元素和上一个元素相等且上一个未被使用，则跳过当前元素”保证两条重复路径只保留一条。第一次写时我很疑惑：为什么条件是上一个未被使用而不是已被使用？想通了才发现，这恰好能在保留一条符合“从左往右扫描”顺序的路径的同时，砍掉另一条因逆序选择导致重复的路径。

3.4 参数传递的陷阱：传引用还是传值

写DFS时，递归函数的参数传递方式非常容易埋雷。拿Java举例，List、数组传的都是引用，如果往path里添加一个元素后不删除，进入返回上一层时path已经被修改过了；而如果每次递归都new一个List，就能保证互不干扰，但代价是频繁分配对象，时间和内存成本都上去了。Python也类似，list传的是引用，path[:]浅拷贝是常用的副本方式。

我个人的习惯是：能用回溯恢复状态的，就尽量共享同一个数据结构；只有在数据规模小、代码逻辑复杂到难以理清恢复顺序时，才用每层拷贝的方式。比如搜索二叉树路径，要求返回所有从根到叶子的路径，我倾向于用一个共享path列表，在递归返回前pop掉当前节点；而如果题目是分层处理某个状态快照，比如棋盘的当前局面快照，那每层复制一份更安全，省去一堆手动恢复的麻烦。

共享数据结构省内存，但每行代码都要想着“在哪里恢复”；拷贝式数据结构思路简单，但时间和空间开销都翻倍。这道选择题没有绝对标准，我看到很多竞赛选手的代码习惯也不一样。我对自己的训练要求是：先在纸上画出递归树，看每个状态在被兄弟分支共享时有没有冲突，再决定用哪种方案。

4. 实操推演：两个高频题型的完整实现

4.1 岛屿数量：图连通域搜索的标答姿势

随便翻开LeetCode的热题榜，“岛屿数量”都是排得上号的。题目描述很简单：一个二维网格，1代表陆地，0代表水，水平或垂直相邻的1属于同一个岛屿，问一共有多少个岛屿。我第一次做这道题时没有立刻想到DFS，因为它的输入是二维数组而不是显式的图结构。但仔细想想，每个格子就是图里的一个节点，相邻的上下左右四个格子就是它的邻接节点。

用DFS解的话，思路极其直观：遍历整个网格，每遇到一个值为“1”的格子，就把它当成一个岛屿的起点，岛屿数量加一，然后从这个格子开始DFS“感染”所有和它相邻的陆地格子——把它们全部改成“0”或者其他已访问标记。这样后续遍历再遇到“0”时就会自然跳过这些已经被处理过的格子，保证每个岛屿只被统计一次。

def numIslands(grid): if not grid: return 0 rows, cols = len(grid), len(grid[0]) directions = [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(r, c): grid[r][c] = "0" # 就地标记，防止重复访问 for dr, dc in directions: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1": dfs(nr, nc) count = 0 for r in range(rows): for c in range(cols): if grid[r][c] == "1": count += 1 dfs(r, c) return count

这段代码有几个细节值得聊。第一个是方向数组directions的写法，用[(1,0), (-1,0), (0,1), (0,-1)]来枚举上下左右四个方向，比手写四段if简洁，可读性也高很多。如果题目扩展成允许八个方向（加上四个对角），只需要往数组里加四个元组，搜索范围立刻变了，代码主体不用动。第二个是边界判断，我习惯把“不越界”和“值为陆地”两个条件合并成一个if写在调用递归之前，这样递归函数内部不需要再判断自己脚下的格子是不是合法，逻辑更清晰。

还有一个关键差异点：这道题的标记不需要回溯。原因我在前面提过，岛屿题的目标是“把连通块全部找到并标记”，而不是“枚举从每个格子出发的所有路径”。如果我在递归返回后把grid[r][c]恢复成“1”，那么同一块陆地的不同格子会在外层遍历时被再次当成新岛屿起点，计数直接翻倍。第一次做的时候我就犯过这个错，把岛屿数量的答案跑出来比预期大了好几倍，盯着调试器看了半天才意识到是恢复标记惹的祸。

4.2 全排列与组合总和：回溯思想的集中体现

排列和组合是DFS回溯最典型的练兵场。全排列的目标是对给定数组的全部元素做一次无重复排列，输出所有顺序。核心是“每个位置选择尚未使用的元素，选完后标记，进入下一个位置；返回时撤销标记”。我在第2节里给出的三参数框架就是为这类题量身定做的。用nums = [1, 2, 3]来推演第一层递归：level=0时，for循环尝试把1、2、3分别放到第一位。选了1之后，level=1的循环只能在{2, 3}里选，这样一路下去，到level=3就把一个完整排列存入result，然后沿着递归栈一路上还状态，尝试其他分支。整个过程和我在草稿纸上画的决策树完全吻合。

组合总和类的题目则更考验对“去重”和“剪枝”的理解。以“组合总和 II”为例：给定数组candidates = [10, 1, 2, 7, 6, 1, 5]和目标值8，要求找出所有和为8的组合，每个数字在每个组合中只能使用一次，且组合之间不能重复。

def combinationSum2(candidates, target): candidates.sort() result = [] path = [] def dfs(start, remaining): if remaining == 0: result.append(path[:]) return for i in range(start, len(candidates)): if i > start and candidates[i] == candidates[i - 1]: continue num = candidates[i] if num > remaining: break path.append(num) dfs(i + 1, remaining - num) path.pop() dfs(0, target) return result

实现里有三个细节是精华。第一是排序，排序让所有相等的元素挨在一起，去重就能用“相邻相等就跳过”的方式实现；同时排序后的数组天然递增，一旦当前元素已经大于剩余目标值remaining，后面更大的元素也必然大于remaining，可以立即break退出循环，这就是剪枝。第二是去重条件if i > start and candidates[i] == candidates[i-1]，它保证同一层递归中相等元素只被用一次，但不影响更深层递归里使用之前已经选过的那个元素——比如candidates排序后是[1, 1, 2, 5, 6, 7, 10]，第一个1和第二个1相邻，当start等于0时第一个1可以选，选完进入下一轮start变成1，此时第二个1在i=1、start=1的位置，i并不大于start，所以仍然可以选。这样既避免了两个1在同一次循环里被重复当开头，又不妨碍同一条组合里出现两个1。第三是目标值递减的处理方式，remaining从target开始，每次递归减去选中的数字，到0时说明凑齐了一组答案。这比传当前和再和target比较更直观，少写一行加法。

这份代码我反复练了很多遍，如今闭着眼也能写出来，但第一次独立完成时完全不是这个状态——我当时没有排序，导致重复组合爆炸；没有剪枝，导致大量明显不可能的分支还在递归。所以说初学者不要怕写出又慢又卡的版本，那都是必经阶段。关键是理解每一步优化在干什么，为什么能省时间。

5. 调试经验：DFS里最常见的四个坑

5.1 无限递归与死循环

DFS最让人头疼的故障之一就是无限递归。程序跑起来不报错，但就是停不下来，最后要么栈溢出，要么系统卡死。最常见的两个原因：一是递归函数里缺少终止条件，或者终止条件写错，导致永远到不了递归出口；二是在图结构中访问了已经访问过的节点，形成一个环，DFS在环里永远绕圈。

第二个原因在无向图里尤其典型。A和B相邻，A的DFS会走到B，B的DFS又会走回A，如果没有访问标记，来回往复无穷尽。解决办法就是前面说过的used或visited标记，在进入一个节点时立即标记，并且通过标记判断是否继续访问。我吃过一次亏是在一个二维迷宫的DFS里，递归方向写得正确、边界判断也正确，但漏了“当前格子是否已被访问”的判断，结果路径在两条通道之间来回横跳，我盯着控制台看了三分钟才反应过来。所以我的习惯就是：所有涉及图或棋盘搜索的DFS，进入递归的第一件事就是确认“访问状态”处理到位，而不是先想路径怎么走。

5.2 重复解与漏解

重复解集中在排列组合类题目，漏解则往往与剪枝条件过强有关。前面提到过排序去重，这里再补充一种常见遗漏姿势：如果递归循环里没有包含“跳到下一个元素”的选项，也就是组合类题目漏掉了“不选当前元素”这个分支，那么枚举出的组合必须从左到右严格取，但凡有一个元素跳过没选就会直接漏掉整个方案。我当初学子集枚举时，自己写的循环逻辑只包含了“选当前元素”而没有“跳过当前元素”，结果[1, 2, 3]的子集永远枚举不出{1, 3}，因为一旦选了1之后，我的代码要求第二层必须在2和3里选一个，不支持从1直接跳到3。这个问题的本质是对决策树每一层分支的定义不够完整——要么显式写选或不选两个分支，要么用start参数控制“下一个可选元素索引”。

5.3 深递归导致的栈溢出

“栈溢出”这题我在Python里见过太多次。默认递归深度1000，对树相关题目通常绰绰有余，但棋盘遍历、网格DFS这类题很容易超。年少的我用过sys.setrecursionlimit(1000000)，写着很爽，但这其实是“拔高天花板”而非“降低楼层”——系统栈仍然会随着递归加深而真实消耗内存。在数据规模达到网格几十万格时，就算上限调了也可能把内存打爆。更稳妥的替代方案是手动模拟栈，把递归改成循环加list的pop和append。这在代码可读性上做了一点牺牲，但对于“非递归不可”的极端场景是必要的。面试的时候如果时间和空间都允许，可以先写递归版本，再口头说“如果数据规模更大，可以改成显式栈”。

5.4 时间复杂度估算失误

DFS的时间复杂度不能用一句“O(n)带过”敷衍掉。它和时间复杂度直接取决于决策树的规模。全排列来说，复杂度是O(n!)，因为第一层有n个选择，第二层n-1个，第三层n-2个，相乘下来就是阶乘级别。子集枚举是O(2^n)，每层两个分支。组合总和类题目因为剪枝的存在，实际运行远低于理论上限，但最坏情况下依然是指数级。

所以在做DFS题时，我习惯在动手前先估一下解空间大小，再决定是否值得用DFS。n=20的全排列已经是天文数字，任何剪枝都救不回来，必须换思路；n=20的子集枚举勉强可跑，加上剪枝也许能压一压。面试时候考官如果问“你这个DFS会不会超时”，能把这种递推关系讲清楚，比支支吾吾说“应该不会吧”要加分得多。

6. 从day44到题感形成：我的经验总结

打卡第44天，回头看这批DFS练习，我觉得真正拉开差距的不是“会写模板”，而是“能根据题目重新定义搜索状态”。排列、组合、子集、岛屿计数、二叉树路径、棋盘搜索，这些题表面各不相同，但抽象到底层都是“在一棵决策树上从根走向叶子”。区别在于树的形态、节点的含义、剪枝的强度各不相同。模板能帮你跨出第一步，但想真正用好DFS，必须学会自己画出那棵树，在纸上标出哪些分支是重复的、哪些分支注定失败、哪些分支需要保存现场之后再走。

还有一个我觉得非常值得养成的习惯：每做完一道DFS题，就把递归调用的栈展开过程手写一遍。别看这费时间，它几乎是我从“凭感觉写”跨越到“不慌不忙调bug”的分水岭。以前一遇到结果不对，我就乱猜哪个条件该加、哪个标记该删，浪费半小时；现在一遇到问题，我先在草稿纸上画出递归树，对照标注状态变化的顺序，很快就能定位是哪个分支在返回时没有正确恢复现场。

如果你也正处在刷题打卡的早期阶段，我的建议是别急着一口气做十道DFS题，而是分三个步子来：第一步，只看三道经典题，全排列、子集、岛屿数量，把三种决策树形态吃透；第二步，自己动手改改条件，比如把组合题加上去重要求、把全排列改成允许重复元素，观察代码里哪里需要调整；第三步，梳理自己的剪枝策略，把所有能用上的优化写进代码并实测时间消耗。走完这三步，你的DFS就不再是“背下来的模板”，而是长在自己脑子里的方法。

第45天我打算接着练基于DFS的进阶变体，比如记忆化搜索和状态压缩DFS。它们本质上还是在用DFS的骨架，只是多了一层缓存或更紧凑的状态表示。我觉得到了那个阶段再回头看今天的这些笔记，应该会有更立体的一层理解。