Sum of product of elements in every subsets of an array

Question

I need to find sum of product of element in every subset of an array in polynomial time complexity.

e.g., for array {1,2,3} required sum will be equal to null+1+2+3+(1*2)+(1*3)+(2*3)+(1*2*3).

All I know is brute-force approach to this problem. Can someone explain how to solve this problem using dynamic programming in O(n^2) or O(n^3) time complexity?

Here's a similar question where they specify subset size. http://stackoverflow.com/questions/10106193/sum-of-product-of-subsets — FriedSaucePots, Oct 12 '15 at 18:51
I want dynamic approach to this problem...can this problem be solved using dynamic programming ? — Akhilesh Yadav, Oct 13 '15 at 06:07

score 1 · Answer 1 · edited May 13 '17 at 10:41

1

Here's a way to solve this in O(n) from: http://www.geeksforgeeks.org/sum-products-possible-subsets/

The closed form for this for a set {a,b,c,...,z} is:

(a+1)(b+1)(c+1)...(z+1) - 1

edited May 13 '17 at 10:41

nomem

1,568
4
17
33

answered May 13 '17 at 06:44

Fatema

11
2

While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - [From Review](/review/low-quality-posts/16111995) – greg-449 May 13 '17 at 10:27
This was my first time answering, thank you for your review! – Fatema May 15 '17 at 13:17

Sum of product of elements in every subsets of an array

1 Answers1