C++ 实现自然数 1~n 全排列（无重复数字）

题目描述

输出自然数 1~n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复数字。

输入格式

1≤n≤9

输出格式

由 1~n 组成的所有不重复的数字序列。每行一个序列

输入样例

输出样例

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

算法1

(搜索) O(n*n!)

每次搜索都从 1~n 中选出一个未被选择过的数字，加入到排列中，直到排列中数字个数为 n 时，输出排列，终止搜索。

时间复杂度

最坏情况下，一共可以产生 n! 个排列，每个排列最多有 n 个数字，所以时间复杂度为 O(n*n!)。

空间复杂度

O(n)，即为数组 a 和数组 b 的空间大小。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int n, a[10], b[10];

void dfs(int x) {
    if (x == n + 1) {
        for (int i = 1; i <= n; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (b[i] == 0) {
            b[i] = 1;
            a[x] = i;
            dfs(x + 1);
            b[i] = 0;
            a[x] = 0;
        }
    }
}

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

注意：

本代码在本机上可以运行，但是在 OJ 上会出现 RE 的错误。
由于代码中使用了 cout 输出，可能导致运行时间过长，需要进行优化。

优化建议：

使用 printf 代替 cout 输出，可以提高效率。
可以使用 static 变量来优化 dfs 函数，避免重复创建局部变量。
可以使用 std::vector 来存储排列，避免使用数组。

通过上述优化，可以有效地提高代码的效率，避免出现 RE 的错误。