DFS暴搜

DFS爆搜：重要的是先确定一个搜索的顺序
回溯的时候注意一定别忘恢复现场

本题题解

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

const int N = 10;

int n;
int path[N]; //path[i]记录第i个位置放哪个数
bool st[N];

void dfs(int step) //step表示当前在放第几位数
{
    if(step == n + 1){
        for(int i = 1; i <= n; i++) printf("%d ", path[i]);
        cout << endl;
        return ;
    }
    for(int i = 1; i <= n; i++){ //每次从1开始看，就是字典序从小到大
        if(!st[i]){
            st[i] = true;
            path[step] = i;
            dfs(step + 1);
            st[i] = false;
        }// path[]不需要恢复，因为会覆盖
    }
}
int main()
{
    cin >> n;
    dfs(1);
    return 0;
}

不需要回溯的代码版本：

留个坑