https://www.geeksforgeeks.org/sum-products-possible-subsets/
Given an array of n non-negative integers. The task is to find the sum of the product of elements of all the possible subsets. It may be assumed that the numbers in subsets are small and computing product doesn’t cause arithmetic overflow.
Example :
Input : arr[] = {1, 2, 3}
Output : 23
Possible Subset are: 1, 2, 3, {1, 2}, {1, 3},
{2, 3}, {1, 2, 3}
Products of elements in above subsets :
1, 2, 3, 2, 3, 6, 6
Sum of all products = 1 + 2 + 3 + 2 + 3 + 6 + 6
= 23
An Efficient approach is to generalize the whole problem into some pattern. Suppose we have two numbers a and b. We can write all possible subset products as:-
= a + b + ab = a(1+b) + b + 1 - 1 = a(1+b) + (1+b) - 1 = (a + 1) * (b + 1) - 1 = (1+a) * (1 + b) - 1
Now take three numbers a, b, c:-
= a + b + c + ab + bc + ca + abc = a + ac + b + bc + ab + abc + c + 1 - 1 = a(1+c) + b(1+c) + ab(1+c) + c + 1 - 1 = (a + b + ab + 1)(1+c) - 1 = (1+a) * (1+b) * (1+c) - 1
The above pattern can be generalized for n numbers.
