C++ 算法：字典序输出 1 到 n 的所有排列

思路：回溯法

回溯法是一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化把这个候选解从候选解的列表中删除。回溯法可以看成是对一棵树的深度优先遍历过程。

在本题中，我们可以将数字 1∼n 看成是一个数组，使用回溯法来枚举所有可能的排列顺序。具体地，我们定义一个使用 vis 数组记录每个数字是否使用过，并从小到大枚举每个位置填哪个数字。当所有位置都填完时，我们就找到了一个排列。

时间复杂度

生成一个排列的时间复杂度为 O(n)，一共有 n! 个排列，因此总时间复杂度为 O(n×n!)。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

vector<int> permutation;
vector<bool> vis;

void backtrack(int n, int cur) {
    if (cur == n) {
        for (int i = 0; i < n; i++) {
            cout << permutation[i] << " ";
        }
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            vis[i] = true;
            permutation[cur] = i;
            backtrack(n, cur + 1);
            vis[i] = false;
        }
    }
}

int main() {
    int n;
    cin >> n;
    permutation.resize(n);
    vis.resize(n + 1, false);
    backtrack(n, 0);
    return 0;
}