PP4889 全排列（基础）

这道题要我们把 1 到 n 的所有排列都列出来，每个数字只能使用一次，并且按从小到大（字典序）的顺序输出。n 最大是 9，全排列最多 362880 个，数量不小，需要用深度优先搜索（DFS）配合回溯来枚举。

解题思路

第一步，理解全排列。 比如 n=2 时，1 和 2 能组成的两位数只有 12、21 两个，11、22 这种重复使用数字的都不算。题目要求把每个排列单独输出一行，数字之间用空格隔开。

第二步，设计搜索状态。 用一个数组 ans 记录当前已经排好的数，用一个标记数组 used 记录每个数字用过没有。函数 dfs(k) 表示正在决定排列的第 k 位是谁：从 1 到 n 从小到大逐个尝试数字 i，如果 i 还没用过，就把它放进 ans[k]，标记 used[i]=1，然后递归调用 dfs(k+1) 去决定下一位；递归返回后再把 used[i] 改回 0，这一步叫"回溯"，是为了让别的排列也能使用数字 i。

第三步，得到字典序。 因为每一位都是从小到大尝试数字的，所以搜索出来的排列顺序天然就是从小到大。n=2 时，先固定第 1 位是 1，第 2 位尝试 2，得到 1 2；回溯后第 1 位变成 2，第 2 位是 1，得到 2 1。

第四步，输出结果。 当 k 大于 n 时，说明 n 位都排满了，就把 ans[1] 到 ans[n] 依次输出，每个数字后面跟一个空格，然后换行。这样每行末尾带一个空格也不会影响判题。

第五步，注意边界。 n=1 时只有一个排列 1；数组要开到比 n 大，比如 12 个元素，防止 n=9 时越界；标记数组和答案数组都要记得在使用前清零。

参考代码

// 输出1~n的所有全排列，每行一个，按从小到大顺序
#include <iostream>
using namespace std;

int n;
int ans[12];   // 当前排列
int used[12];  // 标记数字是否用过

void dfs(int k) {
    if (k > n) { // 排满n位输出
        for (int i = 1; i <= n; i++) cout << ans[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) { // 从小到大选数字保证字典序
        if (!used[i]) {
            used[i] = 1;
            ans[k] = i;
            dfs(k + 1);
            used[i] = 0; // 回溯
        }
    }
}

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

复杂度分析

复杂度分析：全排列一共有 n! 个，每个排列输出时要输出 n 个数字，所以时间复杂度是 O(n·n!)。n<10 时 n! 最大为 362880，乘上 n 也只有三百多万次操作，速度很快。空间上只需要 ans 和 used 两个数组，都是 O(n)。