子集生成的两种方法

刘汝佳算法入门经典 中的子集生成的研究心得

问题解决的首要的方法和步骤是什么？

是大概的想一下问题的细节还是先把问题搞清楚？很多人回答是先把问题搞清楚但是 有谁直接这样做？

是吧！咱们的思维就像how to solve it中所说的一样要想解决问题首先要做的就是弄清楚这个问题是什么,不是这么早得去考虑问题的细节，这样容易挫败自己解决问题的雄心。

废话少说

问题描述如下：

输入input

4

输出output

0
01
012
0123
013
02
023
03
1
12
123
13
2
23
3

研究一下问题的特点每段数据的头一个字母是

0 1 2 3

但是每段字母的以后的顺序却是字典顺序 既是先三个的从小到大 然后两个的从小到大

通过分析数据的特性估计你就会对这个问题的感受更加深刻！

#include
#include
#include
#include
void print_subset(int n,int *A,int cur)//通过递归法来实现子集的生成
{                                      //从0开始到n的序列生成
    for(int i=0;i    printf("%d",A[i]);                 //输出
    printf("\n");                      //每个序列之间由换行隔开
    int s=cur?A[cur-1]+1 : 0;         //如果cur=0的话  s=0  如果cur=1时候s=1
    for(int i=s;i    {
        A[cur]=i;   //每一次从s开始 到 n的赋值
        print_subset(n,A,cur+1);//打印出得数的个数  却是从cur+1开始到n 也就是输出的个数会逐渐减少
    }
}
int main()
{
    int n,a[10];
scanf("%d",&n);
 for(int i=0;i  a[i]=i+1;
 print_subset(n,a,0);
 return 0;
}

下面采用位向量法来说明！

如下图：