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