深入明白全排列算法：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：存储当前生成的排列。
[*] dt（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未被使用
path = i;// 选择i
dt = true;// 标记为已使用
dfs(u + 1); // 递归填充下一位
dt = false; // 回溯：恢复状态
}
}
}
3. 主函数
int main() {
scanf("%d", &n);
dfs(0);// 从第0位开始生成排列
return 0;
}递归过程模拟（以n=2为例）
初始状态
[*] n = 2（排列长度为 2，数字为 1, 2，对应内部 0, 1）。
[*] path = [?, ?]（未初始化）。
[*] dt = （初始均未使用）。
递归调用树
第一层调用：dfs(0)
[*] 当前位 u = 0（正在添补 path）。
[*] 循环 i = 0：
[*] dt 为 false，选择数字 0（实际输出为 1）。
[*] 更新状态：
[*] path = 。
[*] dt = 。
[*] 递归进入 dfs(1)。
第二层调用：dfs(1)
[*] 当前位 u = 1（正在添补 path）。
[*] 循环 i = 0：
[*] dt 为 true，跳过。
[*] 循环 i = 1：
[*] dt 为 false，选择数字 1（实际输出为 2）。
[*] 更新状态：
[*] path = 。
[*] dt = 。
[*] 递归进入 dfs(2)。
第三层调用：dfs(2)
[*] 终止条件：u == n（2 == 2），打印当前排列：
[*] 输出 path+1, path+1 → 1 2。
[*] 返回上一级（回溯到 dfs(1)）。
回溯到 dfs(1)
[*] 恢复状态：
[*] dt = false（dt = ）。
[*] 循环结束，返回上一级 dfs(0)。
回溯到 dfs(0)
[*] 恢复状态：
[*] dt = false（dt = ）。
[*] 继续循环 i = 1：
[*] dt 为 false，选择数字 1（实际输出为 2）。
[*] 更新状态：
[*] path = 。
[*] dt = 。
[*] 递归进入 dfs(1)。
第二层调用：dfs(1)
[*] 当前位 u = 1。
[*] 循环 i = 0：
[*] dt 为 false，选择数字 0（实际输出为 1）。
[*] 更新状态：
[*] path = 。
[*] dt = 。
[*] 递归进入 dfs(2)。
第三层调用：dfs(2)
[*] 打印排列：path+1, path+1 → 2 1。
[*] 返回上一级（回溯到 dfs(1)）。
回溯到 dfs(1)
[*] 恢复 dt = false（dt = ）。
[*] 循环结束，返回 dfs(0)。
回溯到 dfs(0)
[*] 恢复 dt = false（dt = ）。
[*] 循环结束，程序终止。
最终输出
1 2
2 1 关键步调总结
[*] 递归向下：逐层选择未被使用的数字，更新 path 和 dt。
[*] 回溯向上：在每一层递归返回时恢复 dt 的状态，确保其他分支能精确使用数字。
[*] 终止条件：当 path 填满时立刻输出结果。
递归树图示
dfs(0)
│
├─ i=0 (选1)
│├─ dfs(1)
││├─ i=1 (选2) → dfs(2) → 输出
││└─ 回溯：释放2
│└─ 回溯：释放1
│
└─ i=1 (选2)
├─ dfs(1)
│├─ i=0 (选1) → dfs(2) → 输出
│└─ 回溯：释放1
└─ 回溯：释放2关键点总结
[*] DFS的作用：递归地尝试全部大概的数字选择，直到填满整个排列。
[*] 回溯的必要性：在递归返回时恢复 dt 数组的状态，确保后续分支能精确选择数字。
[*] 时间复杂度：O(N×N!)，因为共有 N! 种排列，每种排列需要 O(N) 时间生成。
优化与扩展
[*] 非递归实现：可以用栈模拟递归，避免递归深度过大（但对小规模 n 影响不大）。
[*] 字典序排列：调整循环顺序，使输出按字典序排列。
[*] 去重排列：假如输入包含重复数字，需额外判断避免重复排列。
完备代码（C语言）
通过DFS和回溯的结合，我们可以高效地生成全排列。明白递归的睁开与回溯是掌握该算法的关键。盼望本文的逐步解析能资助你彻底掌握这一经典问题！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]