生成子集

子集问题：写出集合{1~n}的所有子集

提示：共2ⁿ种 增量构造法

一个集合有几个子集，即求从该集合中可取出多少组合在有n个元素的集合中即Cn0 +Cn1+ .....Cnn=2ⁿ

^{增量构造法：}

#include<iostream>
using namespace std;
int n,a[]={1,2,3,4,5,6,7,8,9,10},temp[10]={0};
//temp是存放子集的数组  cur是当前数组下标 pre是上一个存的数 len是要求的子集个数 
void dfs(int temp[],int cur,int pre,int len){
	if(cur==len){
		for(int i=0;i<cur;i++)printf("%d%c",temp[i],i==cur-1?'\n':' ');
		return ;
	}
	for(int i=0;i<n;i++){
		if(a[i]>pre){//子集不能重复 所以要大于上一个的数才能存进去 
			temp[cur]=a[i];
			dfs(temp,cur+1,a[i],len);
		}
	}
}
int main(){
	cin>>n;
	cout<<"空集\n";
	for(int i=1;i<=n;i++){
		dfs(temp,0,0,i);//输出个数为i的子集 
	}
	return 0;
}

位向量法：

这个方法的核心思路是这样：由全集确定其子集只要考虑每个元素的状态是否存在于该子集中即可。

#include<iostream>
using namespace std;//这个方法效率偏低 因为只取一个元素也要遍历完全部 
//n是个数 b是集合 cur是当前下标 
void bitvector(int n,bool b[],int cur){//最后会输出全是false的空集 
	if(cur==n){
		for(int i=0;i<n;i++)if(b[i])printf("%d ",i+1);
		putchar('\n');
		return ;
	}
	b[cur]=true;//丢进集合 
	bitvector(n,b,cur+1);
	b[cur]=false;//不丢进集合 
	bitvector(n,b,cur+1);
}
int main(){
	bool b[100];
	bitvector(4,b,0);
	return 0;
}

二进制法：

算法思想 
例如求4个元素 4 3 2 1 的子集。
那么用二进制的1代表每一位是否选中。
十进制 二进制 
0 0000  代表空集
1 0001  代表{1}
2 0010  代表{2}
3 0011  代表{1,2}
4 0100  代表{3}
...
15 1110  代表{4,3,2}

16 1111  代表{4,3,2,1} 

#include<iostream>
#include<cmath>
using namespace std;
int main(){
	int n=4;
	for(int i=0;i<(1<<n);i++){//二进制0~1111 因为1左移n位等价于2^n.子集个数2^n-1 
		for(int j=0;j<n;j++){//j是用于左移的位数 
			if(i&(1<<j))printf("%d ",j+1);//比如i=0110,j=1,1<<j=0010,i&j监测s的哪一位为1，为1的话输出 
		}
		printf("\n");
	}
	return 0;
}