先说个很多备赛同学都会踩的坑：蓝桥杯省赛前心里对 DFS 挺有底，觉得递归加回溯模板嘛，背下来不就完事了。可真在考场上遇到“排列组合加限制条件”或者“二维网格加路径计数”的题，往往一写就是大半天，要么超时，要么样例全过提交却拿不到分。我复盘过不少这类代码，问题几乎都集中在同一个地方：DFS 到底搜的是什么状态，回溯回来要还原到什么程度，这不是背模板能解决的。
这篇算法日记第二篇就想把 DFS 和回溯模板这件事彻底掰开。我会按“为什么要用、模板长什么样、不同题型的模板变体、剪枝怎么加、拿到题从哪想起、哪些坑最常见”这个顺序展开，写得偏实战。适合第一次接触蓝桥杯的初学者，也适合已经能做中等难度题但分数一直稳不下来的人。看完之后，你应该能形成一套自己顺手、考场敢直接抄上去的代码习惯。
1. 为什么省赛总把 DFS 和回溯当“必考题”
1.1 把近年题面翻一遍，搜索类问题占了多大比重
如果你认真翻过蓝桥杯省赛真题，会发现搜索类问题基本每场都在，无非是换张皮。常见形式有这么几类：把 1 到 9 排成一列，要求相邻位置满足某个条件；从一堆物品里选若干件，要求总体积不超过某个值；在 n 乘 n 棋盘上放东西，要求不同时放在冲突位置；或者在一张地图上找连通块、数路径条数。
这些题的共同点是：题干不需要多高深的数学背景，只要能照着规则把方案枚举出来，就能得分。出题人特别偏爱这种题，因为它同时考察三件事：你对状态空间理解得是否准确、能不能写出不重不漏的枚举、会不会在枚举太慢时用剪枝优化。而这三件事恰好是新手最容易折叠的地方。
我见过不少同学把精力全压在动态规划上，觉得搜索“谁不会”，结果到考场上反而在简单搜索题上卡住。原因很简单：动态规划是“想明白以后代码很短”，DFS 是“代码很短但状态细节极多”，两者出错的方式完全不同。省赛这种中等题为主的环境里，搜索题的性价比非常高。
1.2 省赛阶段，回溯是性价比最高的“保分手段”
说句实在话，省赛不是国际大学生程序设计竞赛，不要求你每道题都拿出满分解。很多编程大题，只要暴力的枚举思路对，测试点里的小数据部分就能拿分。DFS 加剪枝就是一套“看得见的暴力”：把搜索树展开，再用限制条件砍掉不可能的子树，思路清晰、代码模板化，任何人都能上手。
相比学习动态规划需要先想状态定义、再推转移方程、还要处理边界，DFS 的门槛低得多。你不需要理解太多理论，只要能回答“下一步还能选什么”，就能写出第一版。这也是为什么省赛题的答案里，搜索解法非常常见。对于目标是省一、省二的同学，我的建议很直接：动态规划可以不会做难题，但 DFS 回溯模板绝对不能生疏。
1.3 先统一概念：DFS、回溯、暴力枚举是什么关系
很多新手纠结：DFS 和回溯是不是一个东西？我的简化理解是：DFS，深度优先搜索，是一种遍历方式；回溯，是一种枚举策略，核心是“试一下、不行退回来再换”。回溯借助 DFS 去展开决策树，但这棵决策树并不是先建好再遍历的，而是在递归过程中动态生成的。
“暴力枚举”是更大的概念。你用三重 for 循环也是暴力枚举，但一旦枚举维度不确定，比如要选 k 个数、k 是输入参数，for 的层数就没法固定，这时候 DFS 的价值就出来了。回溯本质上就是一个“层数不固定、但每层可选项明确”的 for 循环。把这句话刻在脑子里，很多模板变体就都顺了。
2. 回溯模板的三要素：选择列表、路径、终止条件
2.1 一套直接用得上的回溯骨架
写 DFS 回溯前，有三样东西必须提前标注：路径，当前已经做的选择；候选空间，下一步还能选哪些；终止条件，什么时候记录答案、什么时候返回。模板骨架我写成这样：
void dfs() { if (终止条件满足) { 记录一份答案; return; } for (候选空间中的每一项 x) { if (剪枝条件成立) continue; 做选择; // path 中加入 x 更新状态; // 标记 x 已用，或者 start 下标后移 dfs(); // 进入下一层 恢复状态; // 让后续分支看到干净的局面 撤销选择; // path 弹出 x } }我写过无数版回溯，最后都落在这个骨架上。不同题型的差别，基本只体现在“候选空间”是数组、是下标、还是 used 标记。模板不需要背太多套，能默写出这一套，剩下全是改参数。
2.2 为什么必须做“撤销选择”
用一个生活例子：你出门旅行收拾行李箱，塞了几件厚衣服，走了几步发现太重，必须把厚衣服拿出来，才能试另一套搭配。DFS 里的撤销选择，就是把“拿出来的厚衣服”放回衣柜，保证下一个分支看到的局面和上一个分支进来之前完全一样。
具体到代码：如果 path 是全局数组，你递归进去之前 push 了一个数，递归返回后不 pop，它会一直留着，最终答案里会混入一堆不该有的元素。used 数组也一样，入分支前标 true，回来必须标回 false，否则后续分支都会把那个数跳过，导致漏解。
我见过更隐蔽的写法错误：有人把恢复操作写成了used[i]=false在前、path.pop_back()在后，这两行的顺序其实也有讲究。最稳的习惯是：先 pop 路径，再恢复 used 一类的状态标记，和做选择时正好反向。保证下一次循环开始前，所有状态都回到这个节点刚进来的样子。
2.3 用拷贝传参能不能行？为什么大家还是爱用全局变量
回溯还有一种写法，是把 path 和 used 直接按值传给下一层：
void dfs(int n, vector<int> path, vector<bool> used);这样每个分支都拿到一份自己的拷贝，天然回退，连 pop 都不用写。缺点也很明显：每次递归都要完整复制数组，路径越长开销越大。蓝桥省赛的数据范围里有时候也能过，但一旦搜索层数深一点，大量拷贝会浪费大量时间。
我一般推荐“全局或成员变量加手动撤销”的写法。优点是只改少数几个变量，效率高；缺点是需要对顺序非常敏感。初学者可以先把两种写法各写一遍，通过对比能更直观地理解“状态到底存在哪里”这件事。等你想清楚了，考场上就不会纠结用哪种风格。
2.4 画决策树：复杂度的直观来源
回溯的复杂度通常写成“分支数的深度次方”或者“阶乘”这类形式。以全排列为例，第一层有 n 个分支，第二层每个分支还有 n 减 1 个，总规模就是 n 的阶乘。组合问题则因为 start 不断向后移动，分支数会快速减少。
我遇到没把握的题，第一步不是推复杂度的公式，而是先拿 n=3 或 n=4 画一棵小决策树，看看叶子数量级。如果感觉突破千万甚至上亿，立刻就要考虑剪枝。这个习惯帮我避免过很多“写完了才发现根本跑不完”的尴尬。
3. 三大常考载体：排列、组合、网格，照着模板改就能用
3.1 全排列类：used 标记加每层从头开始
蓝桥杯有很多“把 1 到 n 排成一列，满足某个约束再统计方案数”的题目。这种题最适合用全排列模板：
const int N = 15; bool used[N]; vector<int> path; void dfs(int n) { if ((int)path.size() == n) { // path 就是一个完整排列，做条件校验或计数 return; } for (int i = 1; i <= n; ++i) { if (used[i]) continue; used[i] = true; path.push_back(i); dfs(n); path.pop_back(); used[i] = false; } }关键点是每层循环都从 1 开始，靠 used 数组过滤已经用过的数字，保证一个排列里没有重复。如果题目给的不是 1 到 n 的连续整数，把数组存下来，used 按下标标记即可。如果你想让输出按字典序排，循环从 1 到 n 天然就是字典序，不用额外排序。
3.2 组合与子集类：start 下标是灵魂
组合和排列最大的区别是组合不关心顺序，所以前一层已经选过的位置，后一层不再碰。模板里一般用 start 参数实现：
int n, k; vector<int> path; void dfs(int start, int cnt) { if (cnt == k) { // path 里就是一个组合 return; } for (int i = start; i < n; ++i) { path.push_back(i); dfs(i + 1, cnt + 1); path.pop_back(); } }这里的dfs(i + 1)表示下一步只能从 i 后面的元素开始选。如果你把i + 1改成i，就等价于同一个数可以重复选，这就是“有放回组合”的变体。第一次写组合题时，很容易误以为“没用 used 数组就是组合”，实际组合的核心是 start 下标，不是 used。排列用 used 是为了防止同一个元素在不同层重复，组合用 start 是为了防止后面的层回到前面的位置，两者解决的问题不同。
子集问题和组合本质一样，区别只是终止条件变成“走到数组末尾”，并且每个中间节点都把当前 path 记成一份答案：
void dfs(int idx) { // 当前 path 就是一个合法子集，按需记录 for (int i = idx; i < n; ++i) { path.push_back(i); dfs(i + 1); path.pop_back(); } }如果题目要求每个元素“选还是不选”，你也可以用两个递归分支来实现，效果一样。我个人更习惯循环版，因为在后续要去重和加剪枝的时候，循环版改起来更直观。
还有一个必须注意的点：递归层数代表“已经选了几个数”，不一定等于“数组处理到哪一位”。很多人写组合题时用if (cnt == k)判断，但脑子里想的却是当前下标，一旦中间走了剪枝，很容易漏解。建议写完之后用一个小数据把输出全列出来，看看数量对不对。
3.3 网格类：四个方向加 visited 标记
网格题是省赛大题的热门，但一定先分清楚两类需求：统计连通块个数，还是统计满足条件的路径条数。模板长这样：
const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int n, m; bool vis[55][55]; void dfs(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= m) return; if (vis[x][y]) return; vis[x][y] = true; for (int t = 0; t < 4; ++t) { int nx = x + dir[t][0]; int ny = y + dir[t][1]; dfs(nx, ny); } }如果只是统计连通块，递归返回后千万不要写vis[x][y] = false。因为你做的是“标记已访问”，目的是让同一个连通块只被数一次；一旦撤销，DFS 会反复回到同一个格子，轻则重复计数，重则直接爆栈。
但如果题目是“从起点到终点有多少条路径，且不能重复经过同一个格子”，那么离开一个格子去尝试其他方向时，必须恢复 visited。原因也很简单：路径搜索时，一个格子在前一个分支被占用了，不代表后一个分支不能再用它。不恢复会把所有绕行的可能全部杀掉。
这两种语义只差两个字，代码却完全相反。我的排查建议是：写代码前先用中文写下“这题标记过的点还让不让第二次走”，再决定撤销不撤销，不要在代码里临时纠结。
3.4 用一张表收拢模板差异
| 题型 | 核心状态 | 下一步状态 | 撤销内容 |
|---|---|---|---|
| 全排列 | used 数组加 path | 每层从 0 开始 | pop 加 used=false |
| 组合或子集 | start 下标加 path | 下一层 start=i+1 | 只 pop |
| 网格连通块 | visited 标记 | 四方向扩展 | 不撤销 visited |
| 网格路径计数 | visited 加步数 | 四方向扩展 | 恢复 visited |
这张表不需要背，适合复习时用来检查自己到底有没有搞懂每类题的状态变化。真正理解了以后，看到新题能自己定位出属于哪一类，代码就自然出来了。
4. 剪枝：模板背熟不难，分数分水岭在“砍树”
4.1 三种最常见的剪枝套路
先统一概念：剪枝是在递归入口或 for 循环里，把不可能产生合法答案的分支提前结束，等价于在决策树上砍掉一部分子树。省赛能用到的，九成是以下三种。
第一种是可行性剪枝：当前状态已经违反题面限制，比如填数字时某格冲突、走迷宫时下一步越界或撞墙，直接返回。第二种是最优性剪枝：你正在累加分数或长度，当前值加上后续最优可能也无法超过已记录答案，直接返回。第三种是顺序去重剪枝：把可选列表排好序，相邻重复元素在同一层只尝试第一个，避免产生完全相同的排列或组合。
4.2 一个经典案例：组合总和去重与排序剪枝
有一类题非常常用：给定候选数组，每个数只能用一次，找出所有和为 target 的组合。经典解法是先排序，然后做 DFS：
vector<vector<int>> ans; vector<int> path; void dfs(vector<int>& a, int start, int rest) { if (rest == 0) { ans.push_back(path); return; } for (int i = start; i < (int)a.size(); ++i) { if (i > start && a[i] == a[i - 1]) continue; // 同层去重 if (a[i] > rest) break; // 排序后的可行性剪枝 path.push_back(a[i]); dfs(a, i + 1, rest - a[i]); path.pop_back(); } }这里的i > start很多人第一次看不懂。它只跳过同一层里和前一个相同的元素，不跳过不同层的相同元素。比如候选是 [1,1,2]，目标 3，有效答案应该是 [1,2] 和 [1,2]，但那是两个不同的“1”作为起点。想避免的只是“第一层选了第二个 1，第二层又选了第一个 1”这类重复。如果写成i > 0，就会把所有相同值的不同分支都砍掉，答案数量会少。
a[i] > rest能直接 break，前提是数组已经排序。当前数都超过剩余目标了，后面只会更大，再用 continue 继续循环已经没有意义。这个剪枝把可行性判断提前到 for 层，省掉了大量无意义的递归调用。
4.3 剪枝也有成本，不是越复杂越好
剪枝判断不是免费的。有人为了去重，每次递归都新建一个集合保存已尝试的值，如果集合创建的开销比剪枝节省的递归还大，反而会变慢。多数省赛题的参数 n 在 10 到 30 左右时，排序加朴素剪枝已经足够；真正需要复杂剪枝的题，状态规模往往已经到百万级以上，那时候我更建议停下来想想 BFS 或动态规划，而不是继续加越来越贵的剪枝条件。
还有一个老经验：剪枝顺序要把最容易触发、判断最便宜的写在最前面。比如网格搜索里，“越界判断”必须写在访问标记之前，让非法分支在访问数组之前就退出；如果先查 vis 再查边界，nx 或 ny 已经越界，代码会出现未定义行为。
5. 拿到省赛搜索题，按这套流程切入才不会懵
5.1 每次动手前先回答五个问题
我看别人的代码或者自己手写，都会先回答五个问题：
- 状态是什么？已经选了哪些东西、下一步还能选什么、当前层数代表什么。
- 答案在哪里记录？是搜到叶子才记录，还是每个中间节点都可能成为答案。
- 用什么排除重复？排列用 used，组合用 start，网格用 visited 或方向限制。
- 剪枝条件有哪些？越界、冲突、超过目标值、已有更优解。
- 复杂度大概什么量级？如果预感会超时，就先不写完整功能，加个计数器跑一次，看看递归调用次数。
这套流程看起来简单，但大多数人是反着来的：先写代码，再想边界，忘了终止条件，最后拿小样例试才发现漏了很多分支。顺序一换，答题效率就会差很多。
5.2 一个可复用的按图索骥过程
举个例子，我遇到“把 1 到 9 排列到九个格子，使相邻格子之和满足某个条件”的题，第一版会写成这样：
int ans = 0; bool used[10]; int p[10]; void dfs(int pos) { if (pos == 9) { if (check(p)) ans++; return; } for (int i = 1; i <= 9; ++i) { if (used[i]) continue; p[pos] = i; used[i] = true; dfs(pos + 1); used[i] = false; } }第一版故意先不剪枝，把 9 的阶乘个排列跑一遍，确认答案计数正确。接下来再优化：因为相邻格子条件只涉及已经填好的部分，等某个位置放下去以后，如果新产生的相邻约束已经非法，就提前不再递归。这个顺序目标很清晰，从正确性到性能一层层改，比一上来就写满剪枝要稳得多。
很多资料教人先想清楚所有剪枝再写代码，但竞赛时间紧，我更建议新手先写对，再改快。蓝桥的一些搜索题，直接跑全排列就能得到不少分，因为测试点里经常有比较小的 n。
5.3 什么时候不应该用 DFS
模板不是万能的。求最短步数、最少操作数，优先用 BFS，因为你在意的不是“能不能走到”，而是“需要几步”，DFS 一条路走到黑很容易搜出大量重复状态。求最短路径长度，考虑 Dijkstra 这类算法，不要用 DFS 硬跑。状态可以合并、重叠子问题明显时，优先动态规划，或者把 DFS 改成记忆化搜索。状态维度极大但限制条件又多，就先想想贪心或数学化简。
我见过最多的翻车就是看到“图”就用 DFS 去求最短路，结果样例过、大数据超时。判断口诀一句话：你关心方案是否存在、有多少种，DFS 很自然；你关心最少几步，BFS 更合适；你会发现同一种情况反复被算很多次，就考虑 DP 或记忆化。
5.4 考场时间分配建议
蓝桥省赛题通常是填空和编程混合。我建议把能套搜索模板的题放在“先用稳定模板拿分”的优先档位。如果一道搜索题调了 20 分钟还没通，不要硬耗，先写一个能枚举小数据的暴力版本提交，部分分真的比 0 分重要得多。很多搜索题稍微改改，小数据能过，大数据交给排序剪枝，分就到手了。
6. 拿出我的错题本：DFS 回溯最常见的几种翻车
6.1 撤销不彻底，共享状态被污染
这是头号错误。最常见的情况是递归函数里不止一个出口：
path.push_back(a[i]); dfs(...); if (某个条件) { return; // 提前返回，后面的 pop 没执行 } path.pop_back();修复方案是尽量让函数只有一个出口，或者把恢复动作放在所有 if 分支之前统一定义。如果实在难以避免，我的习惯是把“选择”和“撤销”封装成一对辅助函数，让每次进入这个递归层级的操作保持对称。
6.2 网格题里 visited 清得不是时候
前文讲过连通块和路径计数方向相反。实际代码里的典型 bug 是：外层跑连通块计数时用 visited 防止重复，里层又想找从当前格出发的最远路径，顺手在函数末尾加了 visited=false，导致外层计数变成死循环。建议不同语义的 visited 用独立变量表示，或者在函数名里直接区分 count 和 route 模式，别让一个数组承担两种互相矛盾的责任。
6.3 递归深度过大，大样例直接出事
C++ 在默认栈上递归几十万层，很可能崩溃；Java 和 Python 的递归限制更明显。所以先看层数：如果路径长度可能到 1e5，不要用朴素 DFS 递归。三种替代方案：把递归改成栈模拟、改用 BFS、缩小状态范围。Python 里可以临时提高递归限制，但内存和时间代价不小；C++ 考场不能随便改栈大小，只能靠迭代写法绕开。
6.4 边界条件差 1，答案数量差很多
排列模板里path.size() == n是边界，有人写成大于号，导致答案只记录越界的路径。组合里cnt == k是边界，有人拿start == n当边界，当 k 远小于 n 时会漏。我给自己定的规矩是：每次写完搜索题，立刻用 n=1、n=2 和小网格跑一遍输出，肉眼过一遍有没有重复和遗漏。三分钟能省三十分钟。
6.5 Python 可变默认参数引发的“幽灵状态”
蓝桥 Python 组选手值得注意。写过下面这种代码的同学不在少数：
def dfs(path=[]): path.append(x) ...这个默认列表在函数第一次定义时就被创建，同一个程序跑多组测试时，上一组的数据会残留。正确写法是从外部传入 path 参数，或者用path + [x]这样生成新列表。第一组数据正常、第二组开始答案全错，大概率就是这个问题。
7. 蓝桥备赛阶段，怎么把回溯练成条件反射
7.1 我的三周训练法
第一周只练模板本身。每天抄写全排列、组合、网格连通块三套模板各一遍，抄完再用手推一组小数据。这一步的目标是：把递归入口、终止条件、撤销顺序练到闭眼能写对。第二周做“改模板”训练，找几道真题或相似题，把全排列改成子集、组合改成有放回、网格连通块改成路径计数，重点观察“状态定义变了之后，撤销动作会不会变”。
第三周强制一题多解。同一个搜索题，先写剪枝前版本，再写剪枝后版本，再想想能不能改成记忆化搜索，最后对比各版本耗时。这个训练看起来费时间，但效果非常明显。我记得自己练过一个 n=30 左右的组合题，朴素回溯分支多到跑不完，加了排序剪枝后递归次数只有几万次，那种反差会让人真正信任剪枝这套方法。
7.2 维护一张自己的反错清单
第六节列的是通用反错清单。更有效的做法是记录自己每次具体错在哪一句话，比如“忘了跳过已用标记”“加剪枝时把目标值算错了”“网格题把 visited 恢复错了”。省赛前两周反复看自己的反错清单，比大量刷新题更能稳分。因为你会丢分的地方，往往不是完全不会，而是“感觉熟但细节没练透”的部分。
7.3 考前最想叮嘱的一句话
模板真的不需要背，把它改成有自己习惯的版本更重要。比如我在排列模板里习惯把路径变量叫 step，把访问标记叫 vis，不是炫技，而是因为我的思维模式就是“当前处于第几步、哪个位置被占用”。你完全可以按自己的理解换名字、换顺序，只要每次写作时，心里能说清每一行在做什么。到了考场上，稳定输出熟悉版本，比临时回忆“标准模板长什么样”可靠得多。
