求一个集合的所有子集(c++实现)

87 阅读 0 评论 58 点赞

我是靠谱客的博主任性抽屉，最近开发中收集的这篇文章主要介绍求一个集合的所有子集(c++实现)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

求一个集合的所有子集就是很简单的一道关于组合的题目，是一个集合内的元素的任意组合。一接触这类的题目，感觉头都大，让我找出三个数的任意组合我都担心找不全，更别提更多的数的组合了。在网上查了解决方法，发现他们的想法真的很神奇，顿时有种豁然开朗的感觉。

首先如果一个n个元素的的集合，子集的个数一共有多少个呢，是2^n个，为什么是2^n个呢，转换一下思路，我们就把有n个元素的集合看作是一个有n位的整型数，整形数二进制位的每一位表示集合中的对应元素，所有的子集中只是有某个元素和没有某个元素的区别，对应二进制位就是1和0。那所有的组合一共有多少呢，就是n位二进制数的大小。所以第一种求子集的解法就是遍历0到2^(n-1)的数，找出每个为1的位并把集合对应位置的元素加入到集合中。

还有一种思路，这里引用一些别人表述：

先来一个直观的例子，比如集合 [1,2,3] ，它的所有子集为 [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]。其中空数组表示空集，其实空集肯定会存在，那么让我们的算法从空集开始。

首先，让我们定义一个结果集 ret =[ [] ], 里面

然后第一步，复制结果集，往里面的所有集合加1， [ [1] ], 然后新旧结果集合并，得到 [[]，[1]]

然后第二步，复制结果集，往里面的所有集合加2， [[]，[1]] 变成[[2], [1, 2]], 然后新旧结果集合并，得到 [[], [1], [2], [1, 2] ]

然后第三步，复制结果集，往里面的所有集合加3， [[], [1], [2], [1, 2] ]变成[[3],[1, 3], [2, 3] [1, 2, 3]], 然后新旧结果集合并，得到 [[], [1], [2], [1, 2] ,[3],[1, 3], [2, 3] [1, 2, 3]]

下面是代码：

/*************************************************************************
    > File Name: find_sub_set.cpp
    > Author: ma6174
    > Mail: ma6174@163.com 
    > Created Time: 2020年01月10日 星期五 21时29分36秒
 ************************************************************************/

#include<iostream>
#include<vector>
#include<string>
#include<memory>
#include<math.h>
using namespace std;
typedef std::shared_ptr<vector<vector<int> > > TDArrPtr;

TDArrPtr GetSubSet(vector<int> &vt)
{
	TDArrPtr ret(new vector<vector<int> >);
	if (vt.size() > sizeof(int))
	{
		return ret;
	}
	unsigned int nCount = pow(2, vt.size());
	for (unsigned int i = 0; i < nCount; i++)
	{
		vector<int> subSet;
		//检查对应的二进制位，为1的位表示集合中需要加入对应位置的数
		for (int j = 0; j < (int)vt.size(); j++)
		{
			unsigned int temp = (1 << j) & i;
			if (0 != temp)
			{
				subSet.push_back(vt[j]);
			}
		}
		ret->push_back(subSet);
	}
	return ret;
}

TDArrPtr GetSubSet1(vector<int> &vt)
{
	TDArrPtr ret(new vector<vector<int> >);
	vector<int> subSet;
	ret->push_back(subSet);
	for (unsigned int i = 0; i < vt.size(); i++)
	{
		unsigned int nCount = ret->size();
		for (unsigned int j = 0; j < nCount; j++)
		{
			ret->push_back((*ret)[j]);
			(*ret)[ret->size() - 1].push_back(vt[i]);
		}
	}

	return ret;
}


int main(int argc, char** argv)
{
	vector<int> vt;
	vt.push_back(1);
	vt.push_back(2);
	vt.push_back(3);
	vt.push_back(4);
	TDArrPtr allSubSet = GetSubSet1(vt);
	for (auto &arr : *allSubSet)
	{
		cout << "{";
		for (unsigned int k = 0; k < arr.size(); k++)
		{
			cout << arr[k];
			if (k != arr.size() - 1)
			{
				cout << ",";
			}
		}
		cout << "}";
		cout << endl;
	}

	cout << endl;
	return 0;
}