输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。 【输入形式】 一个自然数 n(1≤n≤9) 【输出形式】 由 1?n 组成的所有不重复的数字序列，每行一个序列，数字之间用一个空格隔开。 c++

这是一个经典的排列组合问题，我们可以使用回溯算法来解决。以下是一个C++实现的解决方案：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& results) {
    if (path.size() == nums.size()) {
        results.push_back(path);
        return;
    }
    
    for (int i = 0; i < nums.size(); ++i) {
        if (used[i]) continue;
        used[i] = true;
        path.push_back(nums[i]);
        backtrack(nums, used, path, results);
        path.pop_back();
        used[i] = false;
    }
}

int main() {
    int n;
    cin >> n;
    
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        nums[i] = i + 1;
    }
    
    vector<bool> used(n, false);
    vector<int> path;
    vector<vector<int>> results;
    
    backtrack(nums, used, path, results);
    
    for (const auto& result : results) {
        for (int i = 0; i < result.size(); ++i) {
            cout << result[i];
            if (i != result.size() - 1) cout << " ";
        }
        cout << endl;
    }
    
    return 0;
}

这个程序的工作原理如下：

1. 我们首先读取输入的自然数 n。

2. 然后，我们创建一个包含 1 到 n 的数字序列。

3. 我们使用一个布尔数组 `used` 来标记哪些数字已经被使用。

4. 我们定义一个 `backtrack` 函数，它会递归地构建排列：
- 如果当前路径 `path` 的长度等于 n，说明我们找到了一个完整的排列，将其添加到结果中。
- 否则，我们遍历所有数字，对于每个未被使用的数字：
- 标记为已使用
- 将其添加到当前路径
- 递归调用 `backtrack` 继续构建排列
- 移除最后一个数字（回溯）
- 标记为未使用

5. 最后，我们遍历结果并打印每个排列。

这个解决方案的时间复杂度是 O(n!)，因为 n 个数字有 n! 种排列。空间复杂度是 O(n)，用于存储当前路径和 `used` 数组。