第一讲递归与递推例题 AcWing 92. 递归实现指数型枚举

一时失言乱红尘 2023-09-26 21:29 59阅读 0赞

## 第一讲 递归与递推 例题 AcWing 92. 递归实现指数型枚举 ##

### 原题链接 ###

[AcWing 92. 递归实现指数型枚举][AcWing 92.]

### 算法标签 ###

递归

### 思路 ###

依次枚举1-n这n个整数，对于每个数字，存在选择与不选择两种方案

### 时间复杂度 ###

2 n = 2 15 ≈ 3 ∗ 1 0 4 2^n = 2^\{15\}\\approx3\*10^4 2n=215≈3∗104

### 代码 ###

#include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    #define x first
    #define y second
    #define ump unordered_map
    #define pq priority_queue
    using namespace std;
    typedef pair<int, int> PII;
    int n;
    inline int rd(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    // u表示第u个数字 st表示当前状态为st
    void dfs(int u, int st){
        // 枚举完毕
        if(u==n){
        	// 便利答案输出
            rep(i, 0, n){
            	// 判断st的第i位是否为1
                if(st>>i&1){
                    printf("%lld ", i+1);
                }
            }
            puts("");
            return;
        }
        // 否则（非边界情况）有两种选择 未选择该数 st没有改变
        dfs(u+1, st);
        //  选择该数 将st第u位置为1 
        dfs(u+1, st|1<<u);
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        n=rd();
        dfs(0, 0);
        return 0;
    }

### 参考文献 ###

[AcWing 92. 递归实现指数型枚举y总讲解][AcWing 92. _y]

![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 92.]: https://www.acwing.com/problem/content/94/
[AcWing 92. _y]: https://www.acwing.com/video/110/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png