解题思路

全排列就是把 1~n 的所有数按所有可能的顺序排出来。比如 n=3 有 6 种排列。

思路：回溯（深度优先搜索）。

把排列看成 n 个位置，从第 1 个位置开始，逐个确定每个位置放哪个数字：

1. 对第 s 个位置，尝试放 1~n 中还没用过的数字
2. 放好后标记这个数字已用，递归去确定第 s+1 个位置
3. 第 s+1 个位置处理完回来，要恢复标记（回溯），试试别的数字
4. 当所有位置都确定（s == n+1）时，输出这个排列

为什么要回溯（恢复标记）？ 因为第 s 个位置试完数字 1 之后，还要试数字 2，所以用完要释放，让后面的数字也能用。

举例 n=3 的搜索过程：

• 位置1放1，位置2放2，位置3放3 → 1 2 3
• 位置3再试别的（没有），回溯，位置2放3，位置3放2 → 1 3 2
• 继续回溯换位置1的数字……

因为每次都是从小到大尝试数字，所以输出自然就是字典序从小到大。

参考代码

#include <iostream>
using namespace std;

int n, book[10], a[10];

void pl(int s) {
    if (s == n + 1) {  // 所有位置确定，输出
        for (int i = 1; i <= n; i++) cout << a[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {  // 第 s 个位置尝试每个数字
        if (book[i] == 0) {          // 还没用过
            a[s] = i;
            book[i] = 1;
            pl(s + 1);               // 递归下一位置
            book[i] = 0;             // 回溯恢复
        }
    }
}

int main() {
    cin >> n;
    pl(1);
    return 0;
}

复杂度分析

• 时间复杂度：O(N!)，n 的全排列有 n! 个
• 空间复杂度：O(N)，递归深度加标记数组