经典dfs问题

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 10;
int path[N];//用来保存序列
bool st[N];//判重数组,用来判断1~n中的数有没有重复使用 true表示用过了
int n;
void dfs(int u)//表示此时搜索的是第几个空位
{
    if(u > n)//如果超过第n个空位，证明全部空位已经填完了，就直接输出所有空位上面的数字
    {
        for(int i = 1;i <= n;i++)//输出从第一个空位到第n个空位上面的数字
        {
            cout << path[i] << " ";
        }
        cout << endl;
        return;
    }
    for(int i = 1;i <= n;i++)//否则的话，就在1~n这些数当中寻找可以填在该空位上面的数字
    {
        if(!st[i])//首先得判断该数字有没有用过
        {
            path[u] = i;//将该数字填在第u个空位上面
            st[i] = true;//该数字用过了
            dfs(u + 1);//填完这个空位就搜索下一个空位
            st[i] = false;//回溯的时候要记得恢复现场
        }
    }
}
int main()
{
    cin >> n;
    dfs(1);//从第一个空位开始搜索
    return 0;
}