C语言-回溯例2

组合问题

组合：从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合，例如OR = {1,2,3,4}, n = 4, r
= 3则无重组合为：

{1,2,3}; {1,2,4}; {1,3,4}; {2,3,4}.

 1 /****************组合******************/
 2 #include <stdio.h>
 3 
 4 int main()
 5 {
 6     int m,n,a[100];
 7     int i,k,j;
 8     int num;//记录解得个数
 9     int flag;//定义标志位，用于判断是否满足条件
10     printf("输入n(C(n,m)):");
11     scanf("%d",&n);
12     printf("输入m(c(n,m)):");
13     scanf("%d",&m);
14     i=1;
15     a[i]=1;//初始值
16     num=0;
17     while(1)
18     {
19         flag=1;
20         for(k=i-1;k>=1;k--)
21         {
22             if(a[k]>=a[i])//约束条件
23             {
24                 flag=0;
25             }
26         }
27         if(flag && (i==m))//输出解
28         {
29             num++;
30             for(j=1;j<=m;j++)
31             {
32                 printf("%d",a[j]);
33             }
34             printf(" ");
35             if(num%6==0)
36                 printf("
");
37         }
38         if(flag&&i<n)
39         {
40             i++;
41             a[i]=1;//取初值
42             continue;
43         }
44         while(a[i]==n&&i>1)i--;//回溯
45         if(a[i]==n&&i==1)
46         {
47             break;
48         }
49         else
50         {
51             a[i]++;//搜索下一条路径
52         }
53     }
54     printf("
组合数C(%d,%d)=%d",n,m,num);
55     return 0;
56 }

运行结果：