二进制枚举子集模板

二进制枚举子集

n个数有2^n个子集，每个子集对应一个二进制数，二进制数的每一位对应一个数，二进制的位权为0表示子集不包含那个数，二进制数的位权为1表示子集包含那个数

参考博客：https://blog.csdn.net/liangzhaoyang1/article/details/52853207

代码：

#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define ls (r<<1)
#define rs (r<<1|1)
#define debug(a) cout << #a << " " << a << endl
using namespace std;
typedef long long ll;
const ll maxn = 1e4+10;
const ll mod = 998244353;
const double pi = acos(-1.0);
const double eps = 1e-8;
ll a[maxn];
void f( ll n, ll s ) {
    for( ll i = 0; i < n; i ++ ) {
        if( s&(1<<i) ) {
            cout << a[i];
            //n的子集共有2^n个，若s=13(1101),刚i=0,2,3时输出
            //13&(1<<0)->13&1  ==1
            //13&(1<<2)->13&4  ==1
            //13&(1<<3)->13&8  ==1
            // 反例13&（1<<4)->13&16 ==0
        }
    }
    cout << endl;
}
int main() {
    ios::sync_with_stdio(0);
    ll n;
    cin >> n;
    for( ll i = 0; i < n; i ++ ) {
        cin >> a[i];
    }
    for( ll i = 0; i < (1<<n); i ++ ) {
        f(n,i);
    }
    return 0;
}