题意概括

给定一个由 $n$ 个不重复的整数组成的数组，要求按任意顺序返回其所有可能的全排列。

数据范围:

• $1 \le n \le 8$
• 数组中的元素均为整数且互不相同。

基础知识

本题是求解全排列的经典问题，通常使用 深度优先搜索 (DFS) 结合 回溯法 (Backtracking) 来解决。

回溯法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来丢弃该解，即“回溯”到之前的决策点，尝试其他的可能性。

对于全排列问题，我们可以定义一个递归函数 dfs(k)，表示我们正在确定排列中第 k 个位置的元素。

1. 基本思想：从第 0 个位置开始，依次尝试将后面每一个没有被使用过的元素放到当前位置。
2. 具体实现：在 dfs(k) 中，我们遍历从 k 到 n-1 的所有元素。对于每个元素 a[i]，我们将其与 a[k]交换，这样就将 a[i] 固定在了第 k 位。然后，我们递归调用 dfs(k+1) 去解决子问题。
3. 回溯：当子问题 dfs(k+1) 返回后，我们需要将 a[i] 和 a[k] 交换回来，恢复数组的状态，以便尝试将其他元素放在第 k 位。
4. 终止条件：当 k 到达数组末尾（即 k == n）时，说明我们已经构造出了一个完整的排列，此时将其输出即可。

该算法的时间复杂度为 $O(n \times n!)$，因为存在 $n!$ 个排列，输出每个排列需要 $O(n)$ 的时间。空间复杂度为 $O(n)$，主要由递归栈的深度决定。

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

// a: 存储当前排列, k: 当前处理到第k个位置, n: 数组总长度
void dfs(vector<int>& a, int k, int n) {
    // 终止条件: 当处理到最后一个位置之后，说明一个排列已生成
    if (k == n) {
        for (int i = 0; i < n; ++i) {
            cout << a[i] << (i == n - 1 ? "" : " ");
        }
        cout << "\n";
        return;
    }

    // 从当前位置k开始，依次尝试将后面的每个元素换到位置k
    for (int i = k; i < n; ++i) {
        swap(a[k], a[i]);  // 决策：将a[i]放到第k位
        dfs(a, k + 1, n);  // 递归：继续处理下一个位置
        swap(a[k], a[i]);  // 回溯：撤销决策，恢复现场
    }
}

void run() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    dfs(a, 0, n);
}

int main() {
    // 关闭同步流
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    run();

    return 0;
}

/*
样例 1:
输入:
3
1 2 3
输出:
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 2 1 
3 1 2 

样例 2:
输入:
2
0 1
输出:
0 1 
1 0 
*/