【AcWing】842. 排列数字(DFS)

DFS是树形结构，深度优先搜索。
dfs可以算作递归。
横线上填和前面不一样的数字。
每一次向下探索都一条路走到黑，直到不能走再回溯。

#include<iostream>

using namespace std;

const int N=10;

int n;
int path[N];//存放走过的路径
bool st[N];//存放1~n哪个数用过了，全局bool默认为false

void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++) printf("%d ",path[i]);
        printf("\n");
        return;
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){
            path[u]=i;
            st[i]=true;
            dfs(u+1);
            //以下回溯现场
            //path[u]=0; 下一次循环会被覆盖掉，所以不用恢复
            st[i]=false;
        }
    }
}

int main(){
    scanf("%d",&n);
    dfs(0);
    return 0;
}