输入一个数，生成0到n-1 的所有子集：
方法一：增量构造
//----增量构造法----// void print_subset_1(int cur){ //cur现在的长度 for(int i=0; i<cur; ++i) printf("%d ", subset[i]); if(cur != 0) printf("\n"); int start = cur ? subset[cur-1]+1 : 0; for(int i=start; i<n; ++i){ subset[cur] = i; print_subset_1(cur+1); } }
方法二：位向量法
//----位向量法----// void print_subset_2(int cur){ //cur现在的长度 if(cur == n){ for(int i=0; i<n; ++i) if(choose[i]) printf("%d", i); printf("\n"); return ; } else{ choose[cur] = 1; print_subset_2(cur+1); choose[cur] = 0; print_subset_2(cur+1); } }
方法三：二进制法
//----二进制法----// for(int i=0; i< (1<<n); ++i) print_subset_3(i); //0，1，....2^n-1 二进制表示2^n-1就是111...1(n-1个1） void print_subset_3(int cur){ for(int i=0; i<n; ++i) if(cur & (1<<i)) printf("%d", i); printf("\n"); }
总程序：
#include <iostream> #include <algorithm> using namespace std; #define MaxSize 100 int n; int subset[MaxSize]; int choose[MaxSize]; //----增量构造法----// void print_subset_1(int cur){ //cur现在的长度 for(int i=0; i<cur; ++i) printf("%d ", subset[i]); if(cur != 0) printf("\n"); int start = cur ? subset[cur-1]+1 : 0; for(int i=start; i<n; ++i){ subset[cur] = i; print_subset_1(cur+1); } } //----位向量法----// void print_subset_2(int cur){ //cur现在的长度 if(cur == n){ for(int i=0; i<n; ++i) if(choose[i]) printf("%d", i); printf("\n"); return ; } else{ choose[cur] = 1; print_subset_2(cur+1); choose[cur] = 0; print_subset_2(cur+1); } } //----二进制法----// void print_subset_3(int cur){ for(int i=0; i<n; ++i) if(cur & (1<<i)) printf("%d", i); printf("\n"); } int main(){ cin>>n; cout<<"Incremental construction:"<<endl; print_subset_1(0); cout<<"Vector construction:"<<endl; print_subset_2(0); cout<<"Binary construction:"<<endl; for(int i=0; i< (1<<n); ++i) print_subset_3(i); return 0; }
原文：https://www.cnblogs.com/futu-/p/12740039.html