子集生成

增量构造法：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 100005;
int a[maxn];

void print_subset(int n,int *A,int cur){
    for(int i = 0;i < cur;i++)
        cout<<A[i]<<" ";
    cout<<endl;
    int s = cur ? A[cur-1]+1 : 0;
    for(int i = s;i < n;i++){
        A[cur] = i;
        print_subset(n,A,cur+1);
    }
}


int main()
{
    int n;
    cin>>n;
    print_subset(n,a,0);
    return 0;
}

位向量法：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 100005;
int a[maxn];

void print_subset(int n,int *B,int cur){
    if(cur == n){
        for(int i = 0;i < cur;i++)
            if(B[i]) cout<<i<<" ";
        cout<<endl;
        return;
    }
    B[cur] = 1;
    print_subset(n,B,cur+1);
    B[cur] = 0;
    print_subset(n,B,cur+1);

}

int main()
{
    int n;
    cin>>n;
    print_subset(n,a,0);
    return 0;
}

二进制法：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 100005;
int a[maxn];

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

二进制法是最常用的方法。

1<<i代表第i个元素，即二进制中从右向左第几位是1，其他位都是0。

s代表第i个子集。(0 <= i < (2^n))

s&(1<<i)代表依次访问n个元素，其中应该输出哪几位的元素，这里的位代表二进制中第几位的序号。

例如：A 10110

（从右往左）

0 --------序号1

1 --------序号2

1 --------序号3

0 --------序号4

1 --------序号5