Problem description:Please list all of the subsets of a known set including the empty set.
My idea: one thinking of the algorithm backtracking is to generate a tree of subset and the condition of an element in the super set for a subset is either on or off.Hence we can specialize the subset tree to a binary tree and we print once when we reach the bottom of the tree each time.It is also easy to write a program.
1 #include <stdio.h> 2 #define MAX 1000 3 4 int n=3; //the number of the set elements 5 int set[MAX]={1,2,3}; 6 int count=0;//the number of the subset. 7 8 void DFS(int level); 9 void print_set(); 10 11 int main() 12 { 13 DFS(0); 14 return 0; 15 } 16 17 void DFS(int level) 18 { 19 if(level==n) 20 { 21 print_set(); 22 return ; 23 } 24 int save=set[level]; 25 set[level]=0; 26 int index=0; 27 for(index=0;index<2;index++) 28 { 29 DFS(level+1); 30 set[level]=save; 31 } 32 33 } 34 35 void print_set() 36 { 37 int index; 38 count++; 39 printf("%d: {",count); 40 for(index=0;index<n;index++) 41 { 42 if(set[index]!=0) 43 printf("%d ",set[index]); 44 } 45 printf("}\n"); 46 }
