现在的位置: 首页 > 综合 > 正文

List All Of The Subset In Another Method

2013年12月04日 ⁄ 综合 ⁄ 共 1216字 ⁄ 字号 评论关闭

Problem description:Please list all of the subsets of a known set including the empty set.

Thinking: the subset's sum of a super set is (n is the number of the super set element) while a n-bit binary
space could express  numbers too.So our target is to generate all of the binary numbers in n bit space.Before solving the problem,please look at this point:


11111 01111
+                 1
-------------------
11111 10000

When the number add 1,the current bit will become to 0 and generate a carry if it was 1.Next,the previous bit 1 will become 0 with a carry,too.If its current bit is 0 ,it becomes 1 without a carry and stop the
addition.Hence,the program process is clear.

复制代码
 1 #include <stdio.h>
 2 #include <math.h>
 3 #define MAX 1000
 4 
 5 int n=4;// the number of the set elements
 6 int set[MAX]={1,2,3,4};
 7 int path[MAX]={0};
 8 int count=1;
 9 
10 //prototype
11 void print_set();
12 
13 int main()
14 {
15     int sum=(int)pow(2.0,n)-1;
16     int index,index_re;
17     printf("%d:{}\n",count);
18     for(index=0;index<sum;index++)
19     {
20         for(index_re=n-1;index_re>=0;index_re--) 
21         {
22             if(path[index_re]==1) 
23                 path[index_re]=0;
24             else
25             {
26                 path[index_re]=1;
27                 break;
28             }
29         }
30         count++;
31         printf("%d:{",count);
32         print_set();
33     }
34     return 0;
35 }
36 
37 void print_set()
38 {
39     int index;
40     for(index=0;index<n;index++)
41     {
42         if(path[index]!=0) 
43             printf("%d ",set[index]);
44     }
45     printf("}\n");
46 }
复制代码

Reference material: C语言名题精选百则技巧篇 in Chinese.

抱歉!评论已关闭.