枚举子集的三种算法

2017年03月09日 14点热度 0人点赞 0条评论

方法一:增量构造法

#include

#include

using namespace std;

void print(int n,int *a,int cur){

         printf("(");

         for(inti=0;i

         printf("%d",a[i]);

         puts(")");

         intm=cur?a[cur-1]+1:0;//避免cur==0时程序崩溃

         for(inti=m;i

                   a[cur]=i;

                   print(n,a,cur+1);

         }

}

int main(){

         inta[10000]={0};

         intn;

         cin>>n;

         print(n,a,0);

         return0;

}

方法二:位向量法(不是按字典序输出)

  枚举每一位选或者不选,复杂度比方法一略高但更好理解,因为与输出全排列思路差不多,满n位就输出。

#include

#include

using namespace std;

int vis[1000]={0};

void print(int n,int *a,int cur){

         if(cur==n){

                   printf("( ");

                   for(inti=0;i

                   if(vis[i])printf("%d ",i);

                   puts(")");

         }

         else{

                            vis[cur]=1;

                            print(n,a,cur+1);

                            vis[cur]=0;

                            print(n,a,cur+1);

         }

}

int main(){

         inta[10000]={0};

         intn;

         cin>>n;

         print(n,a,0);

         return0;

}

方法三:二进制法 方法二其实与二进制是对应的。

#include

#include

using namespace std;

void print(int n){

         for(inti=0;i<(1<

                   printf("(");

                   for(intj=0;j

                   if(i&(1<

                   puts(")");

         }

}

int main(){

         inta[1000],n;

         cin>>n;

         print(n);

         return0;

}

未经允许不得转载!枚举子集的三种算法

update

纸上得来终觉浅, 绝知此事须躬行。