列出所有子集----------2013年1月3日

       问题描述:列出一个集合的所有子集，包括空子集合。

       我的思路:回溯法的一种思路就是生成一颗子集树，而一个集合中的元素，要么存在于子集中，要么不存在，所以这又特殊化成一颗二叉树了。每当到达二叉树的底端时，就打印一次。很容易写出如下的代码:

#include <stdio.h>
 #define MAX 1000

 int n=3;  //the number of the set elements
 int set[MAX]={1,2,3};
 int count=0;//the number of the subset.

 void DFS(int level);
 void print_set();

 int main()
 {
     DFS(0);
     return 0;
 }

 void DFS(int level)
 {
     if(level==n)
     {
         print_set();
         return ;
     }
     int save=set[level];
     set[level]=0;
     int index=0;
     for(index=0;index<2;index++)
     {
         DFS(level+1);
         set[level]=save;
     }

 }

 void print_set()
 {
     int index;
     count++;
     printf("%d: {",count);
     for(index=0;index<n;index++)
     {
         if(set[index]!=0)
             printf("%d ",set[index]);
     }
     printf("}\n");
 }

        如果你觉得我的文章对你有帮助，请顶一下，非常感谢!