• 自己实现 next_permutaion()
• 真正理解排列的原理

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

int main() {	
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    
    vector<int> a(n);
    iota(a.begin(), a.end(), 0);

    while (true) {
        
        for (int i = 0; i < n; i++) cout << a[i] + 1 << " \n"[i == n - 1];

        int p = -1;
        
        // 从后往前找到第一个变小的数
        // a[p + 1], a[p + 2], ... a[n - 1] 是单调下降的
        for (int i = n - 2; i >= 0; i--) if (a[i] < a[i + 1]) {
            p = i;
            break;
        } 
        
        // [n - 1, n - 2, ..., 0]
        if (p == -1) break;
        
        // 将 [a[p + 1], a[p + 2], ..., a[n - 1]] 翻转
        reverse(a.begin() + p + 1, a.end());
        
        // 找到第 1 个大于 a[p] 的数
        int t = lower_bound(a.begin() + p + 1, a.end(), a[p]) - a.begin();
        
        // 交换 a[p], a[t];
        swap(a[p], a[t]);
    }
    
    return 0;
}

• STL 库中的 next_permutation()
• 最简洁！！

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<int> ans(n);
    for (int i = 0; i < n; i++) ans[i] = i + 1;

    // next_permutation(ans.begin(), ans.end())
    // 用于将 ans 处理成字典序变大的下一个排列, 然后返回 true
    // 如果 ans 的字段序已经最大, 就返回 false
    do {
        for (int i = 0; i < n; i++) {
            cout << ans[i] << " \n"[i == n - 1];
        }
    } while (next_permutation(ans.begin(), ans.end()));

    return 0;
}

• dfs 暴力枚举，
• 必学，方法最常用

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    int m = 0;
    vector<int> ans(n);
    vector<bool> f(n, false);

    // 等价于声明函数 void dfs(int p)
    // 这么写的好处是, 可以在 dfs() 里直接使用局部变量, 不需要开全局变量
    function<void(int)> dfs = [&](int p) {
        // 第 1 步: 写终止条件
        if (p == n) {
            for (int i = 0; i < n; i++) cout << ans[i] + 1 << " \n"[i == n - 1];
            return ;
        }

        // 第 2 步: 解决当前状态, 然后往下递归
        for (int i = 0; i < n; i++) if (!f[i]) {
            // 找到还没用过的 i, 添加到 ans
            ans[m++] = i;

            // 将 i 标记为使用过
            f[i] = true;

            // 往下递归
            dfs(p + 1);

            // 本次递归结束后, 还原状态
            m--, f[i] = 0;
        }
    };

    dfs(0);
    return 0;
}