# 3种列举子集的办法

(soulmachine@gmail.com)
https://github.com/soulmachine/acm-cheat-sheet

1.增量构造法
2.位向量法
3.二进制法

```#include <cstdio>
void print_subset1(int *S, int n, int *P, int cur, int ed)
{
for (int i = ed; i < n; i++)
{
//use S[i]
P[cur] = S[i];
for (int j = 0; j <= cur; j++) printf("%d ", P[j]);
printf("\n");
//don't use S[i]
print_subset1(S, n, P, cur + 1, i + 1);
}
}

void print_subset2(int *S, int n, char *B, int cur)
{
if (cur == n)
{
for (int i = 0; i < n; i++) if (B[i]) printf("%d ", S[i]);
printf("\n");
return;
}
B[cur] = 1;
print_subset2(S, n, B, cur + 1);
B[cur] = 0;
print_subset2(S, n, B, cur + 1);
}

void print_subset3(int *S, int n)
{
for (int i = 1; i < (1 << n); i++)
{
for (int j = 0; j < n; j++)
if (i & (1 << j)) printf("%d ", S[j]);
printf("\n");
}
}
int main()
{
const int n=4;
int S[n];
int P[n];
char B[n];

for(int i = 0; i < n; i++) S[i]=i+1;
print_subset1(S, n, P, 0, 0);
putchar('\n');
print_subset2(S, n, B, 0);
putchar('\n');
print_subset3(S, n);

return 0;
}
```

```D:\>a
1
1 2
1 2 3
1 2 3 4
1 2 4
1 3
1 3 4
1 4
2
2 3
2 3 4
2 4
3
3 4
4

1 2 3 4
1 2 3
1 2 4
1 2
1 3 4
1 3
1 4
1
2 3 4
2 3
2 4
2
3 4
3
4

1
2
1 2
3
1 3
2 3
1 2 3
4
1 4
2 4
1 2 4
3 4
1 3 4
2 3 4
1 2 3 4
```

```with t as(select level l from dual connect by level<=4),
p(lv,path,last)as(select 1,cast(l as varchar(20)),l from t
union all
select lv+1,path||' '||l,l from p,t
where l>last and lv<4)
select * from p;

LV PATH                       LAST
----- -------------------- ----------
1 1                             1
1 2                             2
1 3                             3
1 4                             4
2 1 2                           2
2 1 3                           3
2 1 4                           4
2 2 3                           3
2 2 4                           4
2 3 4                           4
3 1 2 3                         3
3 1 2 4                         4
3 1 3 4                         4
3 2 3 4                         4
4 1 2 3 4                       4
```

```void my_subset4(int *S, const int n)
{
int t[n+1]= {0};
int out[1<<n][2]= {0}; //level,last elem
int path[1<<n][n]= {0}; //set

for(int i=1; i<=n; i++) t[i]=i; //init t
int cnt=1;
for(int i=1; i<=n; i++,cnt++) //first level
{
out[i][0]=1;  //lv == set.size
out[i][1]=t[i]; //last
path[i][0]=1;
path[i][1]=t[i];
}
for(int lv=2,begin=1,end=cnt-1; lv<=n; lv++,begin=end+1,end=cnt-1) //level 2- n
{
for(int idx=begin; idx<=end; idx++) //out[idx]
for(int i=1; i<=n; i++) //t[i]
if(t[i]>out[idx][1])
{
out[cnt][0]=lv;
out[cnt][1]=t[i];
path[cnt][0]=lv;
for(int j=1; j<lv; j++)
path[cnt][j]=path[idx][j];
path[cnt][lv]=t[i];
cnt++;
}
}
for(int i=1; i<cnt; i++,puts(""))
for(int j=1; j<=path[i][0]; j++)
printf("%d ",path[i][j]);
}
```

```void my_subset5(int *S, const int n)
{
int t[n+1]= {0};
int out[1<<n][2]= {0}; //level,last elem
int path[1<<n][n]= {0}; //set

for(int i=1; i<=n; i++) t[i]=i; //init t
int cnt=1;

for(int lv=1,begin=0,end=0; lv<=n; lv++,begin=end+1,end=cnt-1) //level 1- n
{
for(int idx=begin; idx<=end; idx++) //out[idx]
for(int i=1; i<=n; i++) //t[i]
if(t[i]>out[idx][1])
{
//out[cnt][0]=lv;
out[cnt][1]=t[i];
path[cnt][0]=lv;
for(int j=1; j<lv; j++)
path[cnt][j]=path[idx][j];
path[cnt][lv]=t[i];
cnt++;
}
}
for(int i=1; i<cnt; i++,puts(""))
for(int j=1; j<=path[i][0]; j++)
printf("%d ",path[i][j]);
}
```

```void my_subset5(int *S, const int n)
{
int t[n+1]= {0};
int path[1<<n][n+1]= {0}; //set

for(int i=1; i<=n; i++) t[i]=i; //init t
int cnt=1;

for(int lv=1,begin=0,end=0; lv<=n; lv++,begin=end+1,end=cnt-1) //level 1- n
{
for(int idx=begin; idx<=end; idx++) //prior level
for(int i=1; i<=n; i++) //t[i]
if(t[i]>path[idx][lv-1])//last elem
{
path[cnt][0]=lv;
for(int j=1; j<lv; j++)
path[cnt][j]=path[idx][j];
path[cnt][lv]=t[i];
cnt++;
}
}
for(int i=1; i<cnt; i++,puts(""))
for(int j=1; j<=path[i][0]; j++)
printf("%d ",path[i][j]);
}
```