求{1,2,3,...m}的幂集之C语言实现

/*回溯法实现*/

/*Junyi Sun at CCNU*/

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 100

int n_stack[N],r,m,n;

void p_stack(){

int i;

printf("{");

for(i=0;i<r-1;i++)

printf("%d,",n_stack[i]);

if(n_stack[0]!=m-n+1)printf("%d},",n_stack[i]);

else printf("%d}",n_stack[i]);

}

void gen(){

r=0;

n_stack[r++]=1;

while(1){

while(r<n)

n_stack[r++]=n_stack[r-1]+1;

p_stack();

while(n_stack[r-1]<m){

n_stack[r-1]++;

p_stack();

}

while(n_stack[r-1]==m-n+r && r!=0)r--;

if(r==0)return;

n_stack[r-1]++;

}

}

int main(){

printf("Enter the base number:\n");

scanf("%d",&m);

for(n=1;n<=m;n++){

printf("C(%d,%d):{",n,m);

gen();

printf("}\n");

}

return 0;

}

---------------------------------

测试结果:

Enter the base number:

1

C(1,1):{{1}}

Enter the base number:

2

C(1,2):{{1},{2}}

C(2,2):{{1,2}}

Enter the base number:

3

C(1,3):{{1},{2},{3}}

C(2,3):{{1,2},{1,3},{2,3}}

C(3,3):{{1,2,3}}

Enter the base number:

4

C(1,4):{{1},{2},{3},{4}}

C(2,4):{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}

C(3,4):{{1,2,3},{1,2,4},{1,3,4},{2,3,4}}

C(4,4):{{1,2,3,4}}

Enter the base number:

5

C(1,5):{{1},{2},{3},{4},{5}}

C(2,5):{{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}}

C(3,5):{{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5}}

C(4,5):{{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5}}

C(5,5):{{1,2,3,4,5}}