图1：

图2：

时间复杂度 $O(n*n!)$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10;
int n;
int state[N]; //当前所处的状态 0表示还没有放数，1~n表示放了哪个数
bool used[N]; // 在搜索时，还得保证每个数只被用1次，因此在搜时，还要判断当前位置可以用的有哪些，因此要存下每个数是否已被用过 true表示被用过

void dfs(int u) { //依次枚举每个分支，即当前位置可以填哪些数
    if (u > n) {
        for (int i = 1; i <= n; i ++) cout << state[i] << ' ';
        puts("");
        return ;
    }
    for (int i = 1; i <= n; i ++) {
        if (!used[i]) { //要找那些没有用过的数，如果当前没有用过，那当前位置可以填该数，成为一个分支，更新状态，且i用过了，used[i]=true
            state[u] = i;
            used[i] = true;
            dfs(u + 1);

            state[u] = 0; //恢复现场
            used[i] = false; 
        }
    }
}

int main () {
    cin >> n;
    dfs(1); //从前往后枚举，由于state和used是全局变量，因此不需要写到dfs()参数中，dfs()中的参数表示当前枚举到第几位了
    return 0;
}