深度优先搜索（DFS）与回溯算法详解：以全排列问题为例

一、问题引入给定一个整数n将数字1~n排成一排按字典序输出所有排列方案。例如当n3时所有排列为1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1二、算法思想深度优先搜索DFS是一种用于遍历或搜索树或图的算法。它会沿着一条路径尽可能深地搜索直到到达叶子节点或无法继续前进然后回溯到上一个分叉点尝试另一条路径。在全排列问题中我们可以将每个位置看作树的一层每个可用的数字看作一个分支。通过DFS遍历这棵树的所有路径就能得到所有排列。三、代码实现#include iostream using namespace std; const int N 10; // 最多处理n9 int ans[N]; // 存储当前排列 bool mark[N]; // 标记数字是否被使用 int n; // 排列的长度 // DFS函数u表示当前需要填写的位从0开始 void dfs(int u) { // 回头的条件当u等于n时说明已经填满了所有位置 if (u n) { // 输出当前排列 for (int i 0; i n; i) { cout ans[i] ; } cout endl; return; // 返回上一层 } // 枚举当前位置可以填的数字 for (int i 1; i n; i) { // 如果数字i没有被使用过 if (mark[i] false) { mark[i] true; // 标记数字i已被使用 ans[u] i; // 将数字i填入当前位置 dfs(u 1); // 递归填写下一个位置 // 回溯恢复现场 mark[i] false; // 取消标记让数字i可以被重新使用 ans[u] 0; // 可不写因为会被覆盖 } } } int main() { n 3; // 以3为例 dfs(0); // 从第0位开始填写 return 0; }四、执行过程详解以n3为例让我们一步步跟踪代码的执行过程特别关注每一步的状态变化。第一步初始调用主程序调用dfs(0)此时u0表示要从第0个位置开始填数字。当前状态调用栈只有main函数标记数组mark[1]false,mark[2]false,mark[3]false答案数组ans[0]0,ans[1]0,ans[2]0第二步探索第一条路径步骤1进入dfs(0)第一个栈帧不满足u3进入for循环i1mark[1]false进入if语句执行mark[1]trueans[0]1调用dfs(1)此时dfs(0)的循环暂停在i1调用栈变化[main] → [dfs(0)]步骤2进入dfs(1)第二个栈帧不满足u3进入for循环i1mark[1]true跳过i2mark[2]false进入if语句执行mark[2]trueans[1]2调用dfs(2)此时dfs(1)的循环暂停在i2调用栈变化[main] → [dfs(0)] → [dfs(1)]步骤3进入dfs(2)第三个栈帧不满足u3进入for循环i1mark[1]true跳过i2mark[2]true跳过i3mark[3]false进入if语句执行mark[3]trueans[2]3调用dfs(3)此时dfs(2)的循环暂停在i3调用栈变化[main] → [dfs(0)] → [dfs(1)] → [dfs(2)]步骤4进入dfs(3)第四个栈帧满足u3进入if语句执行for循环for(int i0; in; i) cout ans[i] ;此时ans数组中存储的是完整的排列[1, 2, 3]输出1 2 3执行return返回到dfs(2)的调用点调用栈变化[main] → [dfs(0)] → [dfs(1)] → [dfs(2)] → [dfs(3)] 输出后弹出dfs(3)回到dfs(2)第三步第一次回溯探索第二条路径步骤5回到dfs(2)从dfs(3)返回继续执行i3这次循环的剩余代码执行回溯mark[3]falseans[2]0← 这里将ans[2]恢复为0执行ii变为4检查循环条件43为假循环结束dfs(2)函数结束返回到dfs(1)调用栈变化[main] → [dfs(0)] → [dfs(1)] ← 弹出dfs(2)回到dfs(1)步骤6回到dfs(1)从dfs(2)返回继续执行i2这次循环的剩余代码执行回溯mark[2]falseans[1]0执行ii变为3检查循环条件33为真继续循环此时i3mark[3]false进入if语句执行mark[3]trueans[1]3调用dfs(2)这是新的dfs(2)调用新的栈帧调用栈变化[main] → [dfs(0)] → [dfs(1)] → [新的dfs(2)]步骤7在新的dfs(2)中不满足u3进入for循环i1mark[1]true跳过i2mark[2]false进入if语句执行mark[2]trueans[2]2调用dfs(3)调用栈变化[main] → [dfs(0)] → [dfs(1)] → [新的dfs(2)] → [新的dfs(3)]步骤8在新的dfs(3)中满足u3进入if语句执行for循环for(int i0; in; i) cout ans[i] ;此时ans数组中存储的是新的完整排列[1, 3, 2]输出1 3 2执行return返回到新的dfs(2)调用栈变化[main] → [dfs(0)] → [dfs(1)] → [新的dfs(2)] ← 弹出新的dfs(3)回到新的dfs(2)步骤9回到新的dfs(2)从dfs(3)返回继续执行i2这次循环的剩余代码执行回溯mark[2]falseans[2]0执行ii变为3mark[3]true跳过执行ii变为4循环结束dfs(2)结束返回dfs(1)调用栈变化[main] → [dfs(0)] → [dfs(1)] ← 弹出新的dfs(2)回到dfs(1)步骤10回到dfs(1)从dfs(2)返回继续执行i3这次循环的剩余代码执行回溯mark[3]falseans[1]0执行ii变为4循环结束dfs(1)函数结束返回到dfs(0)调用栈变化[main] → [dfs(0)] ← 弹出dfs(1)回到dfs(0)第四步第二次回溯探索更多路径步骤11回到dfs(0)从dfs(1)返回继续执行i1这次循环的剩余代码执行回溯mark[1]falseans[0]0执行ii变为2检查循环条件23为真继续循环此时i2mark[2]false进入if语句执行mark[2]trueans[0]2调用dfs(1)新的dfs(1)栈帧调用栈变化[main] → [dfs(0)] → [新的dfs(1)]后续过程会以类似的方式继续生成并输出剩余的排列第三次输出[2, 1, 3]第四次输出[2, 3, 1]第五次输出[3, 1, 2]第六次输出[3, 2, 1]五、完整递归树遍历过程为了更清晰地理解整个过程以下是完整的递归树遍历顺序1. dfs(0) i1 → dfs(1) i2 → dfs(2) i3 → 输出 [1,2,3] 2. dfs(0) i1 → dfs(1) i3 → dfs(2) i2 → 输出 [1,3,2] 3. dfs(0) i2 → dfs(1) i1 → dfs(2) i3 → 输出 [2,1,3] 4. dfs(0) i2 → dfs(1) i3 → dfs(2) i1 → 输出 [2,3,1] 5. dfs(0) i3 → dfs(1) i1 → dfs(2) i2 → 输出 [3,1,2] 6. dfs(0) i3 → dfs(1) i2 → dfs(2) i1 → 输出 [3,2,1]每次输出后程序都会回溯到上一个决策点继续尝试其他可能的选择。六、核心机制详解1. 递归深度控制递归函数dfs(u)的参数u表示当前要填写的位置。当u从0增加到3时递归深度也相应增加。当un时表示已经填满了所有位置此时输出结果。2. 循环枚举选择在每个递归层级for循环for(int i1; in; i)会尝试所有可能的数字。通过mark数组避免重复使用数字实现了剪枝优化。3. 回溯恢复现场每次递归调用返回后都会执行mark[i]false和ans[u]0这两行代码是回溯的关键。它们将状态恢复到做出选择之前使得同一个数字可以在其他排列中使用。4. 输出机制输出发生在递归的最深层当un时。此时ans数组中存储了一个完整的排列通过for循环将其输出。每个完整的排列都会触发一次输出。七、算法要点总结递归深度最多递归n层当un时输出结果输出时机在递归最深层当所有位置填满时输出输出次数等于完整路径数即n!次回溯时机在递归调用返回后执行mark[i]false释放数字恢复现场回溯时将ans[u]恢复为0为下次使用做准备循环作用枚举当前位置所有可能的选择字典序输出由于循环从1到n自然按字典序生成排列避免重复通过mark数组确保每个数字只使用一次八、常见疑问解答1. 为什么循环变量i不会在回溯时重置每个递归调用都有自己独立的栈帧保存局部变量如循环变量i。递归返回时恢复到调用前的栈帧i保持递归调用前的值然后执行i继续循环。2. 为什么需要回溯如果不回溯已使用的数字会一直保持标记状态无法在其他路径中使用导致只能生成一条路径。3. 如何理解递归的深度优先算法会先沿着一条路径走到底填满所有位置输出结果后再返回尝试其他路径而不是先尝试所有第一位的选择。九、扩展思考如果要生成组合而不是排列代码如何修改如果数字可以重复使用代码如何修改如果n较大如何优化通过这个例子我们可以看到DFS和回溯算法的强大之处用简洁的代码系统地探索所有可能性。理解这个例子是学习更复杂回溯问题的基础。