【C++蓝桥杯AB组训练营 | 递归与递推】AcWing 92. 递归实现指数型枚举 & AcWing 93. 递归实现组合型枚举AcWing & 94. 递归实现排列型枚举

秒速五厘米 2024-04-27 06:51 70阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞? 收藏✨ 留言✉ 加关注?本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[C++蓝桥杯AB组训练营][C_AB]】  
> ?本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> ?本专栏同时记录C++蓝桥杯AB组各个内容模块的知识点以及题目的学习笔记，望大家能够在蓝桥杯比赛中大放光彩  
> ?希望我们一起努力、成长，共同进步。

#### 目录 ####

*  一、AcWing 92. 递归实现指数型枚举
 *  二、AcWing 93. 递归实现组合型枚举
 *  三、AcWing 94. 递归实现排列型枚举

## 一、AcWing 92. 递归实现指数型枚举 ##

**原题链接：[AcWing 92. 递归实现指数型枚举][AcWing 92.]**

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    
    using namespace std;
    
    const int N = 16;
    int n;
    int st[N]; //st数组表示每个位置的状态，0表示当前位置还未考虑，1表示选择当前位置，2表示不选择当前位置
    
    void dfs(int u)
    {
        
        if(u > n)
        {
        
            for(int i = 1;i <= n;i++)
                if(st[i] == 1) printf("%d ",i);
            printf("\n");
            return;
        }
        
        st[u] = 2;
        dfs(u + 1);
        st[u] = 0; // 恢复现场
        
        st[u] = 1;
        dfs(u + 1);
        st[u] = 0; // 恢复现场
    }
    
    int main()
    {
        
        scanf("%d",&n);
        dfs(1);
        return 0;
    }

## 二、AcWing 93. 递归实现组合型枚举 ##

**原题链接：[点击直接跳转到该题目][Link 2]**

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    
    const int N = 30;
    int n,m;
    int way[N];
    void dfs(int u,int start)
    {
        
        if(u > m)
        {
        
            for(int i = 1;i <= m;i++) printf("%d ",way[i]);
            puts("");
            return;
        }
        
        for(int i = start;i <= n;i++)
        {
        
            way[u] = i;
            dfs(u + 1,i + 1);
            way[u] = 0;
        }
    }
    
    int main()
    {
        
        scanf("%d %d",&n,&m);
        dfs(1,1);
        return 0;
    }

## 三、AcWing 94. 递归实现排列型枚举 ##

**原题链接：[点击直接跳转到该题目][Link 3]**

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    const int N = 10;
    int st[N],n;
    bool used[N];
    
    void dfs(int u)
    {
        
        if(u > n)
        {
        
            for(int i = 1;i <= n;i++)
                printf("%d ",st[i]);
            puts("");
            return;
        }
        
        for(int i = 1;i <= n;i++)
        {
        
            if(!used[i])
            {
        
                st[u] = i;
                used[i] = true;
                dfs(u + 1);
                
                // 恢复现场
                st[u] = 0;
                used[i] = false;
            }
        }
    }
    
    int main()
    {
        
        cin >> n;
        dfs(1);
        return 0;
    }

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[C_AB]: https://blog.csdn.net/m0_74352571/category_12484311.html?spm=1001.2014.3001.5482
[AcWing 92.]: https://www.acwing.com/problem/content/94/
[Link 2]: https://www.acwing.com/problem/content/95/
[Link 3]: https://www.acwing.com/problem/content/96/