增量构造法

还是递归的方法，通过每次添加一个元素到集合里来直接构造子集

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

using namespace std;

void print_subset(int n,int* A,int cur);

int A[8];

int main() {
    print_subset(5,A,0);   
    return 0;
}

void print_subset(int n,int* A,int cur)
{
    int i;
    
    for(i=0;i<cur;i++) printf("%d",A[i]); //输出当前A集合中的元素
    printf("\n");
    /*定序的技巧，让A中的元素从小到大排列*/
    int s = cur?A[cur-1]+1 : 0; /*如果cur为0,则从0开始往A中添加元素，否则从A的最后一个元素+1开始添加*/
    for(i=s;i<n;i++){
        A[cur]=i;
        print_subset(n,A,cur+1);
    }
}

位向量法

不再是直接构造集合，而是通过数组B来标记某个数是否存在于子集之中

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

using namespace std;

void print_subset(int n,int* B,int cur);

int B[8];

int main() {
    print_subset(5,B,0);
    return 0;
}

void print_subset(int n,int* B,int cur)
{
    if(cur==n){
        for(int i=0;i<cur;i++)
            if(B[i]) printf("%d",i);
        printf("\n");
        return;
    }
    B[cur]=1;   //标记cur存在于子集中
    print_subset(n,B,cur+1);
    B[cur]=0;   //取消标记，将cur踢出子集...
    print_subset(n,B,cur+1);
}

二进制法

二进制法也和位向量法一样是去标记一个元素是否存在于子集之中而不是直接去构造子集，但它使用的是二进制位来标记

比如0100011000110111（最右边是0）表示的是0存在，1存在，2存在，3不存在，4存在…14存在，15不存在这样,所以此时集合就是{0,1,2,4,5,9,10,14}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void print_subset(int n,int s);

int A[8];

int main() {
    int n=5;//求{0,1,2,3,4}的子集
    for(int i=0;i<(1<<n);i++) { //1<<n是100000
        print_subset(n, i);
    }
    return 0;
}


void print_subset(int n,int s)
{
    for(int i=0;i<n;i++)
        if(s&(1<<i)) printf("%d ",i);/*这里是通过与运算逐位去看该位是否为1,如果是1则输出*/
    printf("\n");
}