深入理解全排列算法：DFS与回溯的完美结合

全排列问题是算法中的经典问题，其目标是将一组数字的所有可能排列组合列举出来。本文将详细解析如何通过深度优先搜索（DFS）和回溯法高效生成全排列，并通过模拟递归过程帮助读者彻底掌握其核心思想。

---

问题描述

给定一个正整数 n，生成数字 1 到 n 的所有排列。例如，当 n = 3 时，输出应为：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

算法思路

1. 核心变量

• path[N]：存储当前生成的排列。

• dt[N]（bool 数组）：标记数字是否已被使用（避免重复）。

• n：排列的长度（如 n=3 表示生成 1,2,3 的全排列）。

2. DFS递归函数

void dfs(int u) {if (u == n) {  // 终止条件：排列已填满print_permutation();  // 输出当前排列return;}for (int i = 0; i < n; i++) {if (!dt[i]) {  // 如果数字i未被使用path[u] = i;  // 选择idt[i] = true;  // 标记为已使用dfs(u + 1);   // 递归填充下一位dt[i] = false; // 回溯：恢复状态}}
}

3. 主函数

int main() {scanf("%d", &n);dfs(0);  // 从第0位开始生成排列return 0;
}

递归过程模拟（以n=2为例）

初始状态

• n = 2（排列长度为 2，数字为 1, 2，对应内部 0, 1）。

• path = [?, ?]（未初始化）。

• dt = [false, false]（初始均未使用）。

---

递归调用树

第一层调用：dfs(0)

• 当前位 u = 0（正在填充 path[0]）。

• 循环 i = 0：

  1. dt[0] 为 false，选择数字 0（实际输出为 1）。

  2. 更新状态：

     • path = [0, ?]。

     • dt = [true, false]。

  3. 递归进入 dfs(1)。

第二层调用：dfs(1)

• 当前位 u = 1（正在填充 path[1]）。

• 循环 i = 0：

  • dt[0] 为 true，跳过。

• 循环 i = 1：

  1. dt[1] 为 false，选择数字 1（实际输出为 2）。

  2. 更新状态：

     • path = [0, 1]。

     • dt = [true, true]。

  3. 递归进入 dfs(2)。

第三层调用：dfs(2)

• 终止条件：u == n（2 == 2），打印当前排列：

  • 输出 path[0]+1, path[1]+1 → 1 2。

• 返回上一级（回溯到 dfs(1)）。

回溯到 dfs(1)

• 恢复状态：

  • dt[1] = false（dt = [true, false]）。

• 循环结束，返回上一级 dfs(0)。

回溯到 dfs(0)

• 恢复状态：

  • dt[0] = false（dt = [false, false]）。

• 继续循环 i = 1：

  1. dt[1] 为 false，选择数字 1（实际输出为 2）。

  2. 更新状态：

     • path = [1, ?]。

     • dt = [false, true]。

  3. 递归进入 dfs(1)。

第二层调用：dfs(1)

• 当前位 u = 1。

• 循环 i = 0：

  1. dt[0] 为 false，选择数字 0（实际输出为 1）。

  2. 更新状态：

     • path = [1, 0]。

     • dt = [true, true]。

  3. 递归进入 dfs(2)。

第三层调用：dfs(2)

• 打印排列：path[0]+1, path[1]+1 → 2 1。

• 返回上一级（回溯到 dfs(1)）。

回溯到 dfs(1)

• 恢复 dt[0] = false（dt = [false, true]）。

• 循环结束，返回 dfs(0)。

回溯到 dfs(0)

• 恢复 dt[1] = false（dt = [false, false]）。

• 循环结束，程序终止。

最终输出

1 2 
2 1 

关键步骤总结

1. 递归向下：逐层选择未被使用的数字，更新 path 和 dt。

2. 回溯向上：在每一层递归返回时恢复 dt 的状态，确保其他分支能正确使用数字。

3. 终止条件：当 path 填满时立即输出结果。

---

递归树图示

dfs(0)
│
├─ i=0 (选1)
│  ├─ dfs(1)
│  │  ├─ i=1 (选2) → dfs(2) → 输出 [1, 2]
│  │  └─ 回溯：释放2
│  └─ 回溯：释放1
│
└─ i=1 (选2)├─ dfs(1)│  ├─ i=0 (选1) → dfs(2) → 输出 [2, 1]│  └─ 回溯：释放1└─ 回溯：释放2

关键点总结

1. DFS的作用：递归地尝试所有可能的数字选择，直到填满整个排列。

2. 回溯的必要性：在递归返回时恢复 dt 数组的状态，确保后续分支能正确选择数字。

3. 时间复杂度：O(N×N!)，因为共有 N! 种排列，每种排列需要 O(N) 时间生成。

---

优化与扩展

1. 非递归实现：可以用栈模拟递归，避免递归深度过大（但对小规模 n 影响不大）。

2. 字典序排列：调整循环顺序，使输出按字典序排列。

3. 去重排列：如果输入包含重复数字，需额外判断避免重复排列。

---

完整代码（C语言）

       通过DFS和回溯的结合，我们可以高效地生成全排列。理解递归的展开与回溯是掌握该算法的关键。希望本文的逐步解析能帮助你彻底掌握这一经典问题！