用於大型數組大小的Powerset

我想要查找大型數組（最多1500）的powerset的所有子集的總和。我搜索，但無法找到一個有效的算法。用於大型數組大小的Powerset

例子：

array=[1,2,3]

答：

{} -> 0,{1} -> 1,{2} -> 2,{3} -> 3,{1,2} -> 3,{1,3} -> 4,{2,3} -> 5,{1,2,3} -> 6

是否有一個有效的方式來做到這一點？

2014-12-06 kvnt1102

C或C++，挑一個。 – Borgleader 2014-12-06 20:31:55

C++，我在標題 – kvnt1102 2014-12-06 20:39:06

中提到那麼爲什麼用C++ *和* C標記問題？ – Borgleader 2014-12-06 20:40:18

有n個元素的數組有2^n個子集。

每個元素都會出現在其中的一半。

因此，所有子集的總和將是所有元素的總和乘以2 ^n-1。

2014-12-06 20:39:49

我想找到每個子集的總和分別在示例中。 – kvnt1102 2014-12-06 20:42:21

@ kvnt1102這些子集中將會有2^1500個，您是否真的需要單獨分別使用它們？ – 2014-12-06 20:43:44

找到模m爲k的子集的數量有問題 – kvnt1102 2014-12-06 20:47:05

回答