Arrange Numbers

排列数字

给定一个整数 n，将数字 1 ∼ n 排成一排，将会有很多种排列方法

现在，请你按照字典序将所有的排列方法输出

输入格式 共一行，包含一个整数 n

输出格式 按字典序输出所有排列方案，每个方案占一行

数据范围

1

1 ≤ n ≤ 7

输入样例：

1

3

输出样例：

分析

数组 path[N] 存储当前排列的路径
布尔数组 st[N] 记录数字是否已经被使用，避免重复选择
递归 dfs(n, u)，表示当前正在构造第 u 个位置的数字：
- 如果 u == n，说明已经构造完成，将 path 输出
- 否则，遍历 1 ~ n，依次尝试将每个未使用的数字填入 path[u]：
  - 标记该数字为已使用 (st[num] = true)
  - 递归进入下一层 dfs(n, u + 1)
  - 回溯，撤销选择 st[num] = false 以尝试其他方案

时间复杂度

全排列的数量为 n!，每个排列需要 O(n) 的时间输出，总体时间复杂度 O(n * n!)

空间复杂度

递归深度最多为 O(n)（递归栈）
path 和 st 数组均为 O(n)

总体空间复杂度 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


#include <iostream>

const int N = 10;
int path[N];  // 存储当前排列
bool st[N];   // 记录数字是否已使用

void dfs(int n, int u)
{
  if (u == n) // 递归终点：填满 path 数组
  {
    for (int i = 0; i < n; ++ i)
      std::cout << path[i] << ' ';
    std::cout << '\n';
    return;
  }

  for (int num = 1; num <= n; ++ num) // 依次尝试 1~n
    if (!st[num])  // 确保当前数字未使用
    {
      st[num] = true; // 标记为已使用
      path[u] = num;  // 记录当前选择
      dfs(n, u + 1);  // 递归进入下一层
      st[num] = false; // 回溯，撤销选择
    }
}

int main()
{
  int n;
  std::cin >> n;

  dfs(n, 0); // 从第 0 位置开始搜索

  return 0;
}