7.3 子集生成

1、增量构造法:

一次选出一个元素放到集合中,由于集合中的元素是无序的,所以我们从小到大生成所有元素。每次选择的元素都要比之前的大。

image

image

如上图,生成 {1, 2, 3} 的子集过程中的解答树。 共有2^n个节点(8个),每个节点都是解。

 

 

2、位向量法

 

image

每次有选和不选两种情况

{1 ,2 ,3} 子集的解答数 总共有 1+2+4+ … +2^n= 2^(n+1)-1 个节点

 

3、二进制法

用整数的二进制表示来枚举各种子集

空集为0 ,全集为ALL_BITS=(1<<n)-1

 

 

总结之前的排列树和子集树:

image

原文地址:https://www.cnblogs.com/cute/p/3671734.html