1.排列数字 DFS

 

 

 DFS需要考虑搜索顺序

这道题的搜索顺序是：

假定一开始有n个空位了

然后从左往右，从第一位开始填

每一次填的时候，要填的数字不能和前面一样

 回溯时要记得恢复现场

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int ans[N]; //答案
bool vis[N]; //vis[i]等于true时，表示i这个数被用过了
int n;
void dfs(int u) {
    if (u == n) { //所有位置都搜完了
        for (int i = 0; i < n; i++) { //输出
            cout << ans[i] << " ";
        }
        cout << endl;
        return;
    }
    for (int i = 0; i < n; i++) { //枚举当前位置可以填哪个数
        if (!vis[i]) { //如果这个数没有被用到
            ans[u] = i + 1; //把这个数放在当前这个位置上
            vis[i] = true; //标记这个数已经被用过了
            dfs(u + 1); //递归到下一层
            //然后当上面这个dfs结束的时候，就意味着已经把上面这条路全部走完了
            //下面两行是回溯和恢复现场，恢复成原样
            ans[u] = 0;
            vis[i] = false;
        }
    }
}
int main() {
    cin >> n;
    dfs(0); //从第0个位置开始看
    return 0;
}