0

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?

3

1 Answer 1

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 2n-1.

4
  • i want to find sum of each subset separately as in example..
    – kvnt1102
    Dec 6, 2014 at 20:42
  • 2
    @kvnt1102 There are going to be 2^1500 of these subsets, do you really need them all separately? Dec 6, 2014 at 20:43
  • there is a problem to find out number of the subsets whose modulo m is k
    – kvnt1102
    Dec 6, 2014 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. Dec 6, 2014 at 20:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.