如何在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

大多数算法的工作方式是生成所有可能的子集，然后取您想要的子集的长度。

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

考虑一个给定的集合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 != {}

Answer 3

对于子集，规则是

“至少有两个子集: null和集合本身。所有子集的计数始终为= 2^(n)，其中n是集合中的元素数。”

你可以使用递归回溯来解决这个问题。