HJ150 全排列

题目描述

给定一个整数 n，请按字典序输出数字 1~n 的所有排列。

输入描述： 一行一个整数 n (1 ≤ n ≤ 9)

输出描述： 按字典序输出所有排列，每行输出 n 个整数，数字之间用单个空格分隔

示例：

输入：
3

输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

解题思路

这是一道经典的 DFS（深度优先搜索）+ 回溯算法题。

核心思想

1. 字典序保证：由于我们按 1, 2, 3… 的顺序尝试每个数字，自然生成的是字典序
2. 回溯模板：
   • 用 used[] 数组标记哪些数字已被使用
   • 用 path[] 记录当前排列
   • 递归结束后撤销选择（恢复状态）

图解：n=3 的递归搜索树

            [空]
           / | \
          /  |  \
         /   |   \
      选1   选2   选3    ← 第一层：选第一个数
      / \    |\     |\
     /   \   | \    | \
   选2   选3 选1 选3 选1 选2  ← 第二层：选第二个数
   |     |  |   |  |   |
   3     2  3   1  2   1    ← 第三层：选第三个数

完整排列（从根到叶）：
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

回溯过程详解（以生成 [1,2,3] 为例）

步骤  path          used[]          操作
────────────────────────────────────────────
 1    []            [F,F,F]         初始状态
 2    [1]           [T,F,F]         选1，递归
 3    [1,2]         [T,T,F]         选2，递归
 4    [1,2,3]       [T,T,T]         选3，递归
────────────────────────────────────────────
 5    [1,2,3]       [T,T,T]   ←→    长度=3，输出 "1 2 3"，返回
 6    [1,2]         [T,T,F]         撤销3（pop, used[3]=F）
 7    [1,2]         [T,T,F]   ←→    for循环结束，返回
 8    [1]           [T,F,F]         撤销2（pop, used[2]=F）
 9    [1]           [T,F,F]   ←→    继续for，尝试i=3
10    [1,3]         [T,F,T]         选3，递归（生成下一条排列）
...

关键点

• 向下递归：做选择 → 标记 used → 递归
• 向上回溯：返回 → 撤销选择 → 取消标记 → 尝试下一个数

代码实现

n = int(input())
used = [False] * (n + 1)  # 标记数字是否被使用
path = []                 # 当前排列

def dfs():
    if len(path) == n:    # 排列完成
        print(' '.join(map(str, path)))
        return

    for i in range(1, n + 1):
        if not used[i]:   # 如果数字 i 未被使用
            used[i] = True     # 做选择
            path.append(i)

            dfs()              # 递归

            path.pop()         # 撤销选择（回溯）
            used[i] = False

dfs()

代码解析

代码块	作用
used = [False] * (n + 1)	创建标记数组，索引对应数字 1~n
if not used[i]	检查数字 i 是否可用
used[i] = True	标记数字 i 已被使用
path.append(i)	将 i 加入当前排列
path.pop()	移除最后一个元素（回溯关键）
used[i] = False	恢复 i 为未使用状态（回溯关键）

为什么按 1~n 遍历就是字典序？

因为我们在每一层都是从小到大尝试可用数字： - 第一位先选 1，然后递归生成后续所有可能 - 第一位选 1 的全部完成后，才会选 2 - 以此类推…

这天然保证了字典序。

复杂度分析

• 时间复杂度：O(n! × n)
  • 共 n! 个排列
  • 每个排列需要 O(n) 时间输出
• 空间复杂度：O(n)
  • 递归深度最大为 n
  • used 数组和 path 数组各占 O(n)