/*回溯法实现*/
/*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}}
