夜雨聆风一堂课讲清楚深搜与回溯：用“三个同学轮流写试卷”理解全排列
很多同学学完 DFS（深度优先搜索）后，代码能看懂，但自己写不出来。原因很简单——没有理解递归函数在内存中到底是怎么走的。
这篇文章用一个生活化的比喻——“三个同学轮流写三份试卷”，帮你把深搜和回溯的原理刻进脑子里。
一、题目：全排列
从 1 到 n 中选 m 个数，输出所有可能的排列顺序。
比如 n=3, m=2：
1 21 32 12 33 13 2
一共有 3×2 = 6 种。
二、标准代码
#include<bits/stdc++.h>using namespace std;int n, m;int cnt[110]; // cnt[no] = 第 no 个位置填的数字bool vis[110]; // vis[i] = 数字 i 是否已被使用voiddfs(int no){if (no > m) { // 填满了 m 个位置for (int i = 1; i <= m; i++) {cout << cnt[i] << ” ”;}cout << endl;return;}for (int i = 1; i <= n; i++) { // 尝试每个数字if (!vis[i]) { // 数字 i 还没被用vis[i] = true; // 占用cnt[no] = i; // 第 no 个位置填 idfs(no + 1); // 去填下一个位置vis[i] = false; // 释放（回溯）}}}intmain(){cin >> n >> m;dfs(1);return 0;}
初看这段代码，你可能会疑惑：vis[i] = false 到底在干什么？为什么要“释放”？我们把代码和“写试卷”的比喻结合起来看，答案就清晰了。
三、三个同学轮流写试卷
想象这样一个场景：
场景设定
有 3个同学：A、B、C有 3张空白试卷，编号为位置1、2、3有 3个名字：1、2、3规则：每张试卷只能写一个名字，同一个名字不能出现在两份试卷上
目标：输出所有可能的“名字 → 试卷”的分配方案。
这就是一个全排列问题：3 个名字填到 3 个位置，每个名字只能用一次。
四、核心过程：占用 → 深入 → 释放 → 继续
第 1 步：同学A写第 1 张试卷
A拿起第一张试卷，写上名字 1，然后叫B来写第 2 张。
位置1: 1 位置2: 空 位置3: 空第 2 步：同学B写第 2 张试卷
B拿起第二张试卷，尝试写 1，发现 1 已经被A用了，不能重复写。于是B写 2，然后叫C来写第 3 张。
位置1: 1 位置2: 2 位置3: 空第 3 步：同学C写第 3 张试卷
C拿起第三张试卷，尝试写 1（被A用了）、2（被B用了），最后写 3。三张都写完了，输出第一组方案：
1 2 3第 4 步：C擦掉名字（回溯）
C写完后，把第三张试卷上的名字 3擦掉，释放名字 3。这样其他同学才能再用这个名字。
位置1: 1 位置2: 2 位置3: 空第 5 步：B换一个名字继续
C释放后，回到B。B刚才写了 2，现在B也把 2 擦掉，尝试写 3，然后再次叫C来写第 3 张。
C尝试写 1（被A用了）、2（未被使用），于是写 2。输出第二组方案：
1 3 2第 6 步：继续回溯
这个过程不断重复：写完就擦掉，回到上一级，换一个名字，再深入。
最终输出全部 6 种方案：
1 2 31 3 22 1 32 3 13 1 23 2 1
五、把比喻和代码一一对应
no 张试卷 | cnt[no] |
i 被某张试卷写了 | vis[i] = true |
i 还能用 | vis[i] == false |
cnt[no] = i | |
dfs(no + 1) | |
vis[i] = false | |
六、为什么这个比喻讲得清楚？
因为这个比喻把“递归调用栈”的形象感表现出来了：
“叫下一个同学来写” = 递归深入一层，函数调用栈压入新帧 “写完了回到上一个同学” = 递归返回，栈帧弹出 “暂停的位置” = 每个递归函数的局部状态，保存在栈帧中（当前的 no、循环到哪个i）“擦掉名字” = 回溯，释放资源，让其他分支可以用
学生一旦理解了“占用 → 深入 → 释放 → 继续”这个流程，就自然理解了回溯的本质：先选一条路走到底，走不通或走完了就退回来，擦掉上次的选择，换一条路再走。
七、组合数 vs 全排列：关键区别
如果题目是组合（不考虑顺序），比如从 1~5 中选 3 个数，代码会略有不同：
void dfs(int step, int no) {if (no > m) { ... }for (int i = step; i <= n; i++) { // 从 step 开始，保证递增cnt[no] = i;dfs(i + 1, no + 1); // 下一层从 i+1 开始}}
组合不需要 vis 数组，因为 step 参数已经保证了数字递增（1,2,3 会出现，但 1,3,2 不会）。而全排列需要 vis，因为每个位置都可以填任意数字，只要它还没被用过。
这个区别可以用一句话总结：组合用step控制“只往前走”，全排列用vis控制“不重复使用”。
八、总结
深搜与回溯的核心不是记忆代码，而是理解一个过程：
每一步做一个选择，基于这个选择继续下一步；走到底后，撤销这个选择，尝试另一个选择。
就像三个同学轮流写三份试卷：
当前同学写一个名字 叫下一个同学来写 下一个同学写完后，当前同学擦掉自己的名字 换一个名字，再叫下一个同学来
代码是固定的，但理解这个过程是活的。一旦建立了这个画面感，全排列、N皇后、迷宫搜索、子集生成……所有的 DFS 题目都遵循同样的逻辑。把“占用 → 深入 → 释放 → 继续”这个模型刻在脑子里，遇到任何 DFS 回溯题，你都能知道怎么下手。