问题描述:
给定一个集合,比如{1,2,3,4},要生成所有的子集(不包括空集,也就是2^n-1个集合)
注: n个元素集合有2^n个子集.
1.增量构造法
思路:在已有子集的基础上不断增加新的元素,一直到无法继续添加为止. 另外因为我们排序的是数组的索引,是从小到大的,就不会出现重复的了.
参考代码
#include<iostream> #include<cstdio> using namespace std; int A[101];//存放集合元素下标的的数组 void print_subset(int n,int *A,int cur){//cur:当前A序列中元素的个数. for(int i = 0;i < cur;i++){//打印当前集合,每次进入都要进行打印 printf("%d",A[i]); } printf("\n"); int s = cur ? A[cur-1]+1:0; // 确定下一个元素的最小值 for(int i = s; i < n;i++){//从前往后进行枚举 第一次 A 一定包含A[s]元素, 第二轮则是一定包含A[s+1]元素 A序列中的元素一定都是从小到达的 A[cur] = i; print_subset(n,A,cur+1);//继续构造子集. } } int main() { int n; scanf("%d",&n); print_subset(n,A,0); return 0; }
运行结果:
2.位向量法
思路:使用一个数组来进行标记对应位置的元素是否存在,标记位置为0表示不存在,为1表示存在.
参考代码
#include<iostream> #include<cstdio> using namespace std; int B[10]; void print_subset(int n,int *B,int cur){ if(cur==n){ for(int i = 0; i < cur;i++){ if(B[i]){ printf("%d",i); } } printf("\n"); return; } B[cur] = 1;//选第cur个元素 print_subset(n,B,cur+1); B[cur] = 0;//不选第cur个元素 print_subset(n,B,cur+1); } int main() { int n; scanf("%d",&n); print_subset(n,B,0); return 0; }
运行结果
3.二进制法
有点复杂,自己目前还有点迷糊.
#include<cstdio> #include<iostream> using namespace std; void print_subset(int n,int s){ for(int i = 0;i < n;i++){ if(s&(1<<i)){ printf("%d",i); } } printf("\n"); } int main() { int n; scanf("%d",&n); for(int i = 0; i < (1<<n);i++){// print_subset(n,i); } return 0; }
