数的全排列 dfs深度优先搜索-白红宇

数的全排列 dfs深度优先搜索

阅读量：5131 次

发布时间：2019-06-13

本文共 940 字，大约阅读时间需要 3 分钟。

数的全排列。

输入格式:

一个n（n<10），表示长度

输出格式:

按字典序输出长度为n的所有排列，每个排列后需要换行，每个排列数字以空格分开。

输入样例:

在这里给出一组输入。例如：

输出样例:

在这里给出相应的输出。例如：

1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 思路：dfs的简单应用，注意掌握递归的思想......

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5 #include
            
              6 #include
              7 #include
              
                8 #include
               
                 9 using namespace std;10 #define ll long long 11 #define inf 9999999912 13 int n;14 int out[10];15 int book[11];16 17 void dfs(int step)18 {19 if(step==n+1)20 {21 for(int i=1;i<=n;i++)22 printf("%d%c",out[i],i==n?'\n':' ');23 return ;24 }25 26 for(int i=1;i<=n;i++)27 {28 if(book[i]==0)29 {30 out[step]=i;31 book[i]=1;32 dfs(step+1);33 book[i]=0;34 }35 }36 return ;37 }38 int main()39 {40 41 scanf("%d",&n);42 43 dfs(1);44 45 return 0;46 }