【出自TX笔试题】
难度系数：★★★★☆ 被考察系数：★★★★☆
题目描述：
有一个集合，求其全部子集（包含集合自身）。给定一个集合s，它包含两个元素＜a，b＞，则其全部的子集为＜a，ab，b＞。
分析与解答：
根据数学性质分析，不难得知，子集个数Sn与原集合元素个数n之间的关系满足如下等式：Sn=2^n-1。
方法一：位图法
具体步骤如下所示。
（1）构造一个和集合一样大小的数组A，分别与集合中的某个元素对应，数组A中的元素只有两种状态：“1”和“0”，分别代表每次子集输出中集合中对应元素是否要输出，这样数组A可以看作是原集合的一个标记位图。
（2）数组A模拟整数“加1”的操作，每执行“加1”操作之后，就将原集合中所有与数组A中值为“1”的相对应的元素输出。
设原集合为＜a，b，c，d＞，数组A的某次“加1”后的状态为[1，0，1，1]，则本次输出的子集为＜a，c，d＞。使用非递归的思想，如果有一个数组，大小为n，那么就使用n位的二进制。如果对应的位为1，那么就输出这个位；如果对应的位为0，那么就不输出这个位。
例如集合{a，b，c}的所有子集可表示如下：
算法的重点是模拟数组加1的操作。数组可以一直加1，直到数组内所有元素都是1。实现代码如下：
程序的运行结果如下：
{abc}
{ab}
{ac}
{a}
{bc}
{b}
{c}
{}
该方法的缺点在于如果数组中有重复数时，这种方法将会得到重复的子集。
算法性能分析：
这种方法的时间复杂度为O（N*2^N），空间复杂度O（N）。(www.xing528.com)
方法二：迭代法
1）采用迭代算法的具体过程如下：
假设原始集合s=＜a，b，c，d＞，子集结果为r：
第一次迭代：
r=＜a＞
第二次迭代：
r=＜aabb＞
第三次迭代：
r=＜aabbacabcbcc＞
第四次迭代：
r=＜aabbacabcbccadabdbdacdabcdbcdcdd＞
每次迭代，都是上一次迭代的结果+上次迭代结果中每个元素都加上当前迭代的元素+当前迭代的元素。
代码中使用到了vector容器。这个容器记录了这次迭代需要输出的集合，使用容器的目的是为了这次迭代的时候可以参考上次输出的结果。实现代码如下：
程序的运行结果如下：
a
ab
b
ac
abc
bc
c
根据上述过程可知，第k次迭代的迭代次数为2^k-1。需要注意的是，n＞=k＞=1，迭代n次，总的遍历次数为2^（n+1）-（2+n），n＞=1，所以，本方法的时间复杂度为O（2^n）。
由于在该算法中，下一次迭代过程都需要上一次迭代的结果，而最后一次迭代之后就没有下一次了。因此，假设原始集合有n个元素，则在迭代过程中，总共需要保存的子集个数为2^（n-1）-1，n＞=1。但需要注意的是，这里只考虑了子集的个数，每个子集元素的长度都被视为1。
其实，比较上述两种方法，不难发现，第一种方法可以看作是用时间换空间，而第二种方法可以看作是用空间换时间。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
