dfs求全排列

重点
1. 搜索树中每一个节点代表一种状态
2. 不重复：每一个点选择不同的数字，则后面无论选择什么都是一种不同的排列
3. 字典序：每个位置都是先搜小数字，再搜大数字，搜索树中小的数字排列先被搜到

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10;
int path[N];
bool st[N];
int n;

void dfs(int u) {  // 保证不重复，保证按字典序输出
    if (u == n)  {
        for (int i = 0; i < n; i++) cout << path[i] << " ";
        cout << endl;
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (st[i]) continue;
        path[u] = i;
        st[i] = true;
        dfs(u + 1);

        st[i] = false;
    }
}

int main() {
    cin >> n;

    dfs(0);  // 从第0个位置开始搜索，开始排序

    return 0;
}