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~n 中任意三个数的排列，并非完整的全排列。为了解决这个问题，我们可以使用回溯算法。

回溯算法思路：

回溯算法是一种试探性的搜索算法，其基本思想是：

从一个初始状态开始，逐步探索可能的解空间。
对于每个状态，尝试所有可能的下一步操作。
如果当前状态无法继续探索，则回退到上一个状态，尝试其他操作。

在求解全排列问题时，我们可以从第一个位置开始，依次枚举每个位置上放哪个数。如果当前位置的数已经在之前的位置上出现过了，则不再放入当前位置。当所有位置都填好时，就得到了一个排列。

代码实现：

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

int n, a[101], used[101];

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 (!used[i]) {
            a[x] = i;
            used[i] = 1;
            dfs(x + 1);
            used[i] = 0;
        }
    }
}

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

代码解释：

a[i] 数组用来存储当前排列的结果。
used[i] 数组用来记录数字 i 是否已经被使用过。
dfs(x) 函数用来递归地生成全排列。
当 x 等于 n + 1 时，表示所有位置都已经填好，输出当前排列。
对于每个位置 x，遍历所有数字 i，如果数字 i 没有被使用过，则将其放入当前位置，并递归地调用 dfs(x + 1) 生成下一个位置的排列。
回溯时，将数字 i 从当前位置移除，并将 used[i] 设置为 0，以便下次可以使用它。

总结：

本文通过使用回溯算法，成功地实现了自然数 1~n 的全排列，并提供了完整的代码示例和详细的算法解释。希望这篇文章能够帮助您理解回溯算法的原理和应用。