输出一个集合的所有子集合二进制方法实现：递归实现：

86 阅读 0 评论 57 点赞

我是靠谱客的博主平淡心锁，最近开发中收集的这篇文章主要介绍输出一个集合的所有子集合二进制方法实现：递归实现：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

面试遇上了这个问题，思量了会，想到用递归的方式解决这个问题。回来网上搜索了下，发现通过二进制的思想来解决这个问题更容易，下面我把两种解决方式的思想及原码分享出来。

二进制方法实现：

我们都知道,一个含n个元素的集合拥有2^n个子集合,并且不难发现,其中每个子集合都是从0到2^n-1 每个数的二进制格式中0 放弃,1选择的结果。集合{1,2,3}的所有子集合如下所示: {}000 {1}100 {2}010 {1,2}110 {3}001 {1,3}101 {2,3}011 {1,2,3}111 。

#include <stdio.h>
void printSubset(int set[], int count)
/*count: The count of set's elemnts.*/
{
int i, j, k;
int subSetCount = 1 << count; // 子集合的个数
for (i = 0; i < subSetCount; i++)
{
j = i;
k = 0;
printf("{");
while(j)
{
if (j & 1)
{
printf("%d", set[k]);
}
j >>= 1;
k++;
}
printf("}n");
}
}

int main()
{
int a[5] = {1, 2, 3, 4, 5};
printSubset(a, 5);

return 0;

}

递归实现：

递归的思想是当一个集合只有1个元素是，集合的子集合就是元素本身。如果集合的元素个数大于1，那么集合的子集合为：全集 + 出去第一个元素的集合的所有子集 + 第一个元素和去除第一个元素所有子集组合的集合。以递归的思想实现要复杂很多，并且当集合元素过多时造成栈溢出。

#include <stdio.h>

#include <set>

using namespace std;

set<set<int> > getSubset(set<int> input)
{

set<set<int> > result;
if (input.size() == 1) // 集合只有一个元素，子集合就是自己
{
set<int> one;
one.insert(*input.begin());
result.insert(one);
}
else
{
int poped = *input.begin(); // 移除第一个元素，第一个元素本身是一个集合
set<int> aSubset;
aSubset.insert(poped);
result.insert(aSubset);

input.erase(input.begin());
set<set<int> > tmp = getSubset(input); // 递归获取除去第一个元素后集合的所有子集
for (set<set<int> >::iterator it = tmp.begin(); it != tmp.end(); it++)
{
result.insert(*it); // 集合的子集包括了所有去除第一个元素后的子集
set<int> one = *it;
one.insert(poped); // 集合包含了第一个元素和去除第一个元素后集合的所有子集组成的集合
result.insert(one);
}
}

return result;

}

void printSubset(set<set<int> > subsets)
{
for (set<set<int> >::iterator it = subsets.begin(); it != subsets.end(); it++)
{
printf("{");
for (set<int>::iterator itItem = (*it).begin(); itItem != (*it).end(); itItem++)
{
printf("%d", *itItem);
}
printf("}n");
}
}

int main()
{
set<int> mySet;
mySet.insert(1);
mySet.insert(2);
mySet.insert(3);
mySet.insert(4);
printSubset(getSubset(mySet));

return 0;
}