全排列

一句话算法

全排列就是每个位置选择一个还没用过的元素，直到所有位置都填满。

问题模型

给定 n 个互不相同的元素，输出它们的所有排列。

例如输入：

1 2 3

所有排列有：

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

核心直觉

把排列看成 n 个空格。

第 1 个空格可以放任意元素；第 2 个空格只能放剩下的元素；第 3 个空格继续从剩下的元素里选。

所以 DFS 的每一层负责填写一个位置，used[i] 记录第 i 个元素是否已经被前面的位置使用。

算法步骤

1. 用 path[dep] 保存当前排列的第 dep 个元素。
2. 用 used[i] 表示输入中的第 i 个元素是否已经被选择。
3. 定义 dfs(dep)：
   • 如果 dep > n，输出一个完整排列。
   • 否则枚举所有元素 i。
   • 如果 used[i] == false，选择它、递归下一层、再撤销选择。

撤销选择就是回溯，它让同一个元素可以用于另一条搜索路径。

算法证明

关键不变量： 进入 dfs(dep) 时，path[1..dep-1] 是一个没有重复元素的排列前缀。

1. 初始时空前缀没有重复元素。
2. 每次只选择 used[i] == false 的元素，所以扩展后仍然没有重复。
3. 到达 dep > n 时，前缀长度为 n，且没有重复，因此它是一个合法排列。
4. 任意一个合法排列，都能按它第 1 位、第 2 位、… 的选择顺序走出唯一一条 DFS 路径。

所以算法生成的都是合法排列，且每个合法排列恰好生成一次。

复杂度分析

排列数量是 $n!$，每个排列输出 $n$ 个元素。

• 时间复杂度：$O(n \cdot n!)$，不计输出时 DFS 节点数为 $O(n!)$ 量级。
• 空间复杂度：$O(n)$，用于 path、used 和递归栈。

代码实现

        
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

        #include <bits/stdc++.h>
using namespace std;

const int maxn = 10 + 5;

int n;
int a[maxn], path[maxn];
bool used[maxn];

// 枚举输入序列的所有排列。
// dep 表示当前正在填写排列中的第 dep 个位置。
void dfs(int dep) {
    if (dep > n) {
        for (int i = 1; i <= n; ++i) {
            cout << path[i] << (i == n ? '\n' : ' ');
        }
        return;
    }

    for (int i = 1; i <= n; ++i) {
        if (used[i]) continue;
        used[i] = true;
        path[dep] = a[i];
        dfs(dep + 1);
        used[i] = false;
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    dfs(1);
    return 0;
}
    

测试用例

输入：

3
1 2 3

输出：

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

应用分类详解

全排列的本质是枚举“所有元素的一种顺序”。

一、顺序敏感的方案枚举

典型模式： 相同元素集合，不同顺序代表不同方案。

识别信号： 排队、访问顺序、任务顺序、路径顺序。

核心建模： 每一层决定当前位置放哪个未使用元素。

二、搜索和剪枝的基础模型

典型模式： 先写全排列暴力，再根据约束剪掉不可能分支。

识别信号： n 较小、要求最优顺序、约束能在前缀阶段判断。

核心建模： path 是当前顺序前缀，递归过程中及时判断前缀是否合法。

经典例题

• luogu-P1706 全排列问题：全排列入门模板。
• luogu-P1219 八皇后：在排列基础上加入斜线冲突剪枝。
• leetcodecn-46 全排列：练习 used 数组和回溯撤销。

参考

• 本书相关章节：递归实现多重循环