如何在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 != {}