pvpcoder's blog

How to find the sum of all subset of a array ?
By pvpcoder, history, 10 years ago, In English

Suppose if a I have a array A={2,3,5}
Subsets of array={2},{3},{5},{2,3},2,5},{3,5},{2,3,5}
and the sum of all subsets =2+3+5+2+3+5+3+5+2+3+5=40.
Is there any standard algorithm to find sum of all subsets of array ?

  • Vote: I like it
  • -22
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Each Element appears 2N-1 times in the sum. So answer is 2N-1 * Sum Of All Elements Of The Array.

In Your Example Answer is 22 * (2+3+5) = 40.

→ Reply
  • »
    »
    10 years ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it -8 Vote: I do not like it

    Only if all elements are distinct

    Please explain why the answer will be same if all elements are not distinct?

    array=[1,1,1]. In this case, only 1 subset of array is possible {1} because the elements of a set are distinct by definition of set. So answer is 1.

    Its untrue only when, by subset of array you mean elements of set are array indices.

    → Reply
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

It is well known that the number of subsets of a set of n elements in 2n. This can be proved by the multiplication principle, that there are to choices for each element ai: to include or not to include ai in the subset.

Let the n elements be named a0, a1, ..., an - 1. Consider an element ai. The number of subsets in which you include ai thus must be equal to the number of those in which you didn't. This can be proved, but somehow it is obvious.

Thus the number of subsets where ai is included is 2n - 1. This means ai would contribute 2n - 1 times to the sum.

The other elements will work in the same way as above. Thus the final sum is

Rearranging gives . This is clearly 2n - 1 times the sum of the elements of the array.

Sample test on your data: 23 - 1·(2 + 3 + 5) = 40

→ Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

isn't this related to a problem from a running contest ?

→ Reply