作者：未知 来源：月光软件站 加入时间：2005-5-13　月光软件站

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

相关软件：