Powerset for large array size

Question

I want to find the sum of all subsets of a powerset for a large-sized array (up to 1500). I searched but was unable to find an efficient algorithm for this.

Example:

array=[1,2,3]

Answer:

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

Is there an efficient way to do so?

Take a look at this http://stackoverflow.com/questions/728972/finding-all-the-subsets-of-a-set, IMO your questions is kind of dup of it — Shmil The Cat, Dec 06 '14 at 20:43

score 1 · Answer 1 · edited Dec 06 '14 at 20:40

1

There are 2^n subsets of an array with n elements.

Each element will be present in exactly half of them.

Therefore the sum of all subsets will be the sum of all elements multiplied by 2^n-1.

edited Dec 06 '14 at 20:40

Columbo

60,038
8
155
203

answered Dec 06 '14 at 20:39

Peter de Rivaz

33,126
4
46
75

i want to find sum of each subset separately as in example.. – kvnt1102 Dec 06 '14 at 20:42
2

@kvnt1102 There are going to be 2^1500 of these subsets, do you _really_ need them all separately? – Peter de Rivaz Dec 06 '14 at 20:43
there is a problem to find out number of the subsets whose modulo m is k – kvnt1102 Dec 06 '14 at 20:47
1

@kvnt1102 Try solving that problem by using dynamic programming where DP[i][k] gives the number of subsets of the first i elements of your array which have sum equal to k modulo m. – Peter de Rivaz Dec 06 '14 at 20:48

Powerset for large array size

1 Answers1