DFS（6）——hdu1342Lotto

一、题目回顾

题目链接：Lotto

Sample Input

7 1 2 3 4 5 6 7

8 1 2 3 5 8 13 21 34

0

Sample Output

1 2 3 4 5 6

1 2 3 4 5 7

1 2 3 4 6 7

1 2 3 5 6 7

1 2 4 5 6 7

1 3 4 5 6 7

2 3 4 5 6 7

1 2 3 5 8 13

1 2 3 5 8 21

1 2 3 5 8 34

1 2 3 5 13 21

1 2 3 5 13 34

1 2 3 5 21 34

1 2 3 8 13 21

1 2 3 8 13 34

1 2 3 8 21 34

1 2 3 13 21 34

1 2 5 8 13 21

1 2 5 8 13 34

1 2 5 8 21 34

1 2 5 13 21 34

1 2 8 13 21 34

1 3 5 8 13 21

1 3 5 8 13 34

1 3 5 8 21 34

1 3 5 13 21 34

1 3 8 13 21 34

1 5 8 13 21 34

2 3 5 8 13 21

2 3 5 8 13 34

2 3 5 8 21 34

2 3 5 13 21 34

2 3 8 13 21 34

2 5 8 13 21 34

3 5 8 13 21 34

题意：以升序的形式给定k个数，输出从中挑选6个数满足升序的所有情况。

二、解题思路

两个参数，第一个保存当前搜索的位置，第二个保存已挑选的个数。

三、代码

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 const int maxn = 1e4+;

 #define INF 0x3f3f3f3f

 int a[];                //子集S

 int b[];                //存放6个数

 int k;

 bool vis[];

 void dfs(int pos,int num)

 {

     if(num==){

         for(int i=;i<;i++)    printf("%d ",b[i]);

         printf("%d\n",b[]);

         return;

     }

     for(int i=pos;i<k;i++){

         if(!vis[i]){

             vis[i] = ;

             b[num] = a[i];

             dfs(i+,num+);

             vis[i] = ;                    //方便下一次序列继续使用

         }

     }

 }

 int main()

 {

     int kase = ;

     while(cin>>k && !(k==)){

         if(kase++)    printf("\n");        //打印空行

         for(int i=;i<k;i++){            //从0开始

             scanf("%d",&a[i]);

         }

         memset(vis,,sizeof(vis));

         dfs(,);

     }

     return ;

 }

巴特西

DFS（6）——hdu1342Lotto

最新文章

热门文章