如何在C++中生成给定数组的子集？

Question

我想生成一组数字的大小为n = 0, 1, 2, ...的子集。
不应该用不同顺序重复相同的数字，如2-3-4 = 3-2-4 = 4-2-3 = 4-3-2

例如，

vector<unsigned int> list = {2,4,6,8,9} 

这样子集将像，

n=0 {} 

n=1 {2}{4}{6}{8}{9} 

n=2 {2,4}{2,6}{2,8}{2,9}{4,6}{4,8}{4,9}{6,8}{6,9}{8,9} 

Answer 1

生成长度相等的所有二进制数来你的号码的数量。

3 numbers: 
000 
001 
010 
011 
100 
101 
110 
111 

接着根据位置选择的数字，并将它们映射到根据集（即，如果001，你将其映射到图1，用于101你会它映射到3）。

对于初始集合{1,2,3}：

{}  ->0 
{3}  ->1 
{2}  ->1 
{2,3} ->2 
{1}  ->1 
{1,3} ->2 
{1,2} ->2 
{1,2,3} ->3 

我只是给你一个想法，因为这看起来像功课，这不是解决家庭作业现场。这应该给你一个起点。

Answer 2

对于子集，该规则是

“有至少两个子集：空和设定自身的所有子集 计数总是= 2 ^（N），其中n是数。 集中的元素“。

您可以使用recurisve-backtracking来解决这个问题。

Answer 3

大多数算法通过生成所有可能的子集，然后取得你想要的[这里它的长度]。

您可以使用的一个想法是递归。抽象，所以你做你的功课。

考虑一个给定的集合G = {1,2,3}你必须找到它的子集。

保持一组Y = { {} }开始。

Step 1 : 1 may or may not be there . Y = { {1} , {} } . G = {2,3}

Step 2 : 2 may or may not be there . Y = { {1,2} , {2} , {1} , {} } . G = {3} .

答案不言而喻，直到G != {}