递归归纳

普通枚举 普通指数级枚举

💙

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;

const int N=20;

int n;
int st[N];   //0还没有选择  1选择  2不选


void dfs(int c)
{     //终止条件
    if(c>n)
       { 
          for(int i=1;i<=n;i++)  
               {   if(st[i]==1)   //被选中了
                         cout<<i<<" ";
                       
               }
                    cout<<endl;

                   return ; 
        }


    st[c]=2;
    dfs(c+1);

    st[c]=0;


    st[c]=1;
    dfs(c+1);
    st[c]=0; 



}


int main()
{
    
    cin>>n;
    dfs(1);
    return 0;
}

输出结果:

输入

3

输出

1
2
3
4
5
6
7
3 
2 
2 3 
1 
1 3 
1 2 
1 2 3

全排列型枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
const int N=16;

bool use[N];
int st[N];
int n;
void  dfs(int num)   //枚举第num个数字  此时num还没有赋予具体的数值
{  

    if(num>n) { 
        for(int i=1;i<=n;i++)
            {

                cout<<st[i]<<" ";  
            }
        
         cout<<endl;                      
        return  ;} 


    for(int i=1;i<=n;i++)
       {   
           if(use[i]==false)
           
           {use[i]=true;  //第数字i被用了 
            st[num]=i;     //将数字i赋值于 num（枚举的一个数字）
            dfs(num+1);

            use[i]=false;
            st[num]=0;     
            
             }//恢复现场
           



       }
   




}



  

int main()
{   cin>>n;

  dfs(1);



}

输出结果:

输入

3

输出

1
2
3
4
5
6
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

组合型枚举 字典序升序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// 从 1∼n
//  这 n
//  个整数中随机选出 m 个，输出所有可能的选择方案。
 

// 输入格式
// 两个整数 n,m
//  ,在同一行用空格隔开。

// 输出格式
// 按照从小到大的顺序输出所有方案，每行 1个。
//  个

// 首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

// 其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。


#include<bits/stdc++.h>
using namespace std;
const int N=50;

int way[N];

int n,m;

void dfs(int use,int start)  //use 指的是当前枚举到哪个位置，start指的是目前从哪个位置开始枚举 即是从最小的位置开始枚举
  {   
       //递归结束条件
       if(use==m+1) 
         {   
            for(int i=1;i<=m;i++)
                  {
                      cout<<way[i]<<" ";
                  }   
             cout<<endl;
             return;
         }

     for(int i=start;i<=n;i++)
           {
                way[use]=i ;  //当前枚举到use位置  循环赋值
                dfs(use+1,i+1);//继续枚举下一个位置 
                way[use]=0;  //，枚举完一论循环之后  恢复现场
                 
                 
 

           }
         



  }

int main()
{   cin>>n>>m;  
    dfs(1,1);



}

输出结果:

输入 5 3

输出

1
2
3
4
5
6
7
8
9
10
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5