【AcWing】92. 递归实现指数型枚举

发表于 分类于 Valine：
本文字数： 113 阅读时长 ≈ 1 分钟

92. 递归实现指数型枚举

思路

  1. 位运算
第一种
1
2
if(state>>i&1)
//右移i位，与上1，判断第i位是否使用

5=101
5>>1&1=0

7=111
7>>1&1=1

第二种
1
2
dfs(u+1,state|1<<u);
//state或1，左移u位,表示第i位被使用

2=10
2|1<<2=6=110

6|1<<3=14=1110

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;

int n;
void dfs(int u, int state)
{
    if(u==n)
    {
        for(int i=0;i<n;i++)
            if(state>>i&1)
            cout<<i+1<<" ";
        cout<<endl;
        return ;
    }
    dfs(u+1,state);
    dfs(u+1,state|1<<u);
}
int main()
{
    cin>>n;
    dfs(0,0);
    return 0;
}