题解 | #全排列#

题目链接

全排列

题目描述

给定一个整数 $n$ ，请按字典序输出数字 $1, 2, \dots, n$ 的所有排列。

解题思路

这是一个生成全排列的经典问题，可以使用深度优先搜索（DFS）结合回溯法来解决。

1. 核心思想

我们的目标是构建一个长度为 $n$ 的排列。我们可以把它想象成有 $n$ 个空位，我们需要从数字 $1, 2, \dots, n$ 中不重复地选择数字填入这些空位。

第1个位置：可以填入 $1, 2, \dots, n$ 中的任意一个。
第2个位置：可以填入剩下 $n-1$ 个未使用的数字中的任意一个。
...
第n个位置：只能填入最后一个剩下的数字。

这个逐层决策的过程天然形成了递归结构，非常适合用DFS来解决。

2. 回溯算法流程

定义递归函数：创建一个递归函数，例如 dfs(current_permutation)，它负责在当前已构建的部分排列 current_permutation 的基础上，继续构建剩下的部分。
维护状态：我们需要一个状态标记来记录哪些数字已经被使用过了。一个布尔数组 used[1...n] 是一个很好的选择，used[i] 为 true 表示数字 i 已经被放入当前排列中。
递归终止条件：当 current_permutation 的长度达到 $n$ 时，说明我们已经构建好了一个完整的排列。此时，我们打印这个排列，并结束当前递归分支（返回）。
递归过程（循环与选择）：在 dfs 函数内部，我们进行一次循环，从 $1$ 到 $n$ 。在循环中，我们尝试将数字 i 放入当前排列的下一个位置。
- 检查：如果数字 i 尚未被使用（used[i] == false）。
- 选择：
  - 将 i 加入 current_permutation。
  - 将 used[i] 标记为 true。
  - 向下递归：调用 dfs，继续填充下一个位置。
- 撤销选择（回溯）：
  - 当从下一层的递归调用返回后，我们需要“撤销”刚才的选择，以尝试其他的可能性。
  - 将 i 从 current_permutation 中移除。
  - 将 used[i] 恢复为 false。

通过这种“选择-递归-撤销”的模式，我们就能系统地遍历所有可能的排列。为了保证输出是字典序，我们的循环自然地从 $1$ 遍历到 $n$ ，这确保了较小的数字会被优先放在排列的前面。

C++ STL next_permutation 值得一提的是，C++标准库 <algorithm> 中提供了一个非常有用的函数 next_permutation，它可以直接生成序列的下一个字典序排列。使用它可以在几行代码内解决本问题，但在面试或需要手动实现算法的场合，理解和掌握回溯法仍然是必要的。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int n;
vector<int> current_permutation;
vector<bool> used;

void dfs() {
    // 当排列长度达到n时，打印并返回
    if (current_permutation.size() == n) {
        for (int i = 0; i < n; ++i) {
            cout << current_permutation[i] << (i == n - 1 ? "" : " ");
        }
        cout << endl;
        return;
    }

    // 尝试放入数字 1 到 n
    for (int i = 1; i <= n; ++i) {
        if (!used[i]) {
            // 选择
            used[i] = true;
            current_permutation.push_back(i);
            
            // 递归
            dfs();
            
            // 撤销选择 (回溯)
            current_permutation.pop_back();
            used[i] = false;
        }
    }
}

int main() {
    cin >> n;
    used.resize(n + 1, false);
    dfs();
    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

public class Main {
    private static int n;
    private static List<Integer> currentPermutation;
    private static boolean[] used;

    private static void dfs() {
        if (currentPermutation.size() == n) {
            for (int i = 0; i < n; i++) {
                System.out.print(currentPermutation.get(i) + (i == n - 1 ? "" : " "));
            }
            System.out.println();
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!used[i]) {
                used[i] = true;
                currentPermutation.add(i);
                
                dfs();
                
                currentPermutation.remove(currentPermutation.size() - 1);
                used[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        used = new boolean[n + 1];
        currentPermutation = new ArrayList<>();
        dfs();
    }
}

def solve():
    n_str = input()
    if not n_str:
        return
    n = int(n_str)
    
    result = []
    current_permutation = []
    used = [False] * (n + 1)

    def dfs():
        if len(current_permutation) == n:
            # 将生成的排列格式化为字符串并存入列表
            result.append(" ".join(map(str, current_permutation)))
            return

        for i in range(1, n + 1):
            if not used[i]:
                used[i] = True
                current_permutation.append(i)
                
                dfs()
                
                current_permutation.pop()
                used[i] = False
    
    dfs()
    
    # 一次性打印所有结果
    print("\n".join(result))

solve()

算法及复杂度

算法：深度优先搜索（DFS）、回溯法
时间复杂度： $\mathcal{O}(n \cdot n!)$ 。总共有 $n!$ 个排列。对于每一个排列，我们需要 $\mathcal{O}(n)$ 的时间来打印它。生成所有排列的过程本身，如果考虑所有递归树节点的数量，是 $\sum_{k=0}^{n} \frac{n!}{(n-k)!}$ ，数量级也是 $\mathcal{O}(n!)$ 。因此，总时间由打印主导。
空间复杂度： $\mathcal{O}(n)$ 。这包括了存储当前排列 current_permutation 的空间、标记数字是否使用的 used 数组的空间，以及递归调用栈的深度，三者都是 $\mathcal{O}(n)$ 。