dfs+判断数组解决排列

解题思路:

注意事项:
坑：1.题目空了一格输出，输出一个就换行

2.字典序输出

参考代码:

#include<bits/stdc++.h>

const int N=10;//题目默认字典序了strcmp

int n;//要求输出n个数

bool st[N];//判断数组 true表示已经选过这个数，false代表还没选这个数（bool数组默认false）

int a[N];//存答案的数组a

 //p表示当前枚举到哪个位置，从1开始 

void dfs(int p){

    int i;

    if(p>n){

        for(i=1;i<=n;i++){

            printf("%d ",a[i]);//题目空了一格

        }

        printf("\n");

        return ;

    }

    for(i=1;i<=n;i++){

        if(!st[i]){//如果这个数没被选过

            st[i]=true;//选择并标记选过了

            a[p]=i;//将值存入数组

            dfs(p+1);//找下一位

            st[i]=false;//前面选择失败，复原该位

            //a[p]=0;

        }

    }

}

int main(){

    scanf("%d",&n);

    dfs(1);

    return 0;

}