子集的生成

实例

input 

4

output  

1

1 2

1 2 3

1 2 3 4

1 2 4

1 3

1 3 4

1 4

2

2 3

2 3 4

2 4

3

3 4

4

请按任意键继续. . .(第一行是空行表示空集)

第一种方法：增量构造法

顾名思义，就是要用不断在已有子集的基础上不断增加新元素一直到无法继续增加时为止（这种方法的递归边界利用了“定序处理”的方案）

递归核心是这样的

//n 全集的元素数目 //A* 表示已经处理过的集合//cur 表示目前的位置 void zenglianggouzaofa(int n , int* A ,int cur){	//把已经完成的子集打印出来	for(int i=0;i

第二种方法，位向量法 = = 哇塞 好高端的词汇呢

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

所以用一个大数组（= = 就是所谓的位向量 B[]来记录每个元素的两种状态即可）其实用bool就好 不用int也可以

void  bitvector(int n,bool* B,int cur){	if(cur==n){		for(int i=0;i

注意：此种方法效率较第一种低。

因为他要求让所有的元素都要遍历完成时才能输出。这也是为何要cur==n时猜return的原因

另外 此种方法生成子集的顺序稍有不同

（此处空行表示空集）

4

3

3 4

2

2 4

2 3

2 3 4

1

1 4

1 3

1 3 4

1 2

1 2 4

1 2 3

1 2 3 4

请按任意键继续. . .

第三种方法更为高大上了：二进制法

这个呢 和位向量法有一个异曲同工的地方 就是用0,1来表示元素是否在集合内

此时用一个二进制数则非常好的解决了问题 而且还有大量按位运算可以用来对应集合运算，非常方便，效率也很高，主要是数据存储的空间也变小了

三种按位运算：

按位与----------->集合取交集

按位或----------->集合取并集

按位异或运算----------->集合取对称差

= = 第三个是亮点 异或运算还有个特殊的结论是A^B^B=A 不同是1 相同是0

举例 A={1,2,4} B = {2,3}  A=10110 B=01100 A^B=11010

所以A^B={1,4,3}就是将对方有而自己没有的加入进来就是了

void bin(int n){	//比如n=4 1<<4= 10000 = 16 	for(int i=0;i<(1<

结果是

1

2

1 2

3

1 3

2 3

1 2 3

4

1 4

2 4

1 2 4

3 4

1 3 4

2 3 4

1 2 3 4

请按任意键继续. . .