C语言算法—生成数集的所有子集（类似建立树的回溯法）

#include<stdio.h> #include<malloc.h> int N; void build(int *a,int *tag,int n) { if(n==N) { printf("{"); for(int i=0;i<N;++i) if(tag[i]==1) printf("%d",a[i]); printf("}"); printf("\n"); return ; } tag[n]=0;//标记为0之后，开始建立下一个 build(a,tag,n+1); tag[n]=1;//标记为1之后，开始建立下一个 build(a,tag,n+1); } int main() { scanf("%d",&N); int *a=(int *)malloc(sizeof(int)*N); for(int i=0;i<N;++i) scanf("%d",&a[i]); int tag[N]; build(a,tag,0); return 0; }

这种生成数集子集的方法，类似于生成二叉树的方式；

用一个只显示0，1的数组，来表示该位是否显示；而每一位都有0，1两种选择，在每一位选择结束之后，开始以同样的方式来建立其下一个元素（子树）；

而递归结束的条件则是，当n==N时，递归结束；

所以这种写法的主要思路，就是像树一样分支讨论情况。

图片为建立以1，2数集为子集的生成过程：