0

Given a set of n elements, find sum of product of subsets of size at most k ( k is another integer).

The Range of n is in the 1000s so a I need something more faster than exponential time complexity.

I feel this problem might be solved using Polynomial FFT, but I'm not sure. Also, check this out https://math.stackexchange.com/questions/786183/sum-of-multiplication-of-all-combination-of-m-element-from-an-array-of-n-element/788655#788655

For example :

S : {1, 2, 3, 4, 5}

k = 2

Then, the answer will be

1 + 2 + 3 + 4 + 5 + 1*2 + 1*3 + 1*4 + 1*5 + 2*3 + 2*4 + 2*5 + 3*4 + 3*5

Pseudocode or just some pointers as to how to come closer to the solution are higly appreciated.

MathCoder97
  • 9
  • 2
  • You might want to check this out. https://stackoverflow.com/questions/10106193/sum-of-product-of-subsets?rq=1 – JM C Sep 09 '19 at 15:15

1 Answers1

5

Let DP[i][j]: the sum of products of subsets with exactly size j which contains only [1~i]th elements.

Then DP[i][j] = DP[i-1][j] + DP[i-1][j-1] * arr[i]

Now you can solve it on time-complexity O(NK).

== Edit ==

This is a simple code.

int arr[1002]; /// The array where number is located
int DP[1002][1002];
int ans=0; /// final answer
DP[0][0] = 1;
for(int i=1; i<=n; i++){
    DP[i][0] = 1;
    for(int j=1; j<=i && j<=k; j++){
        DP[i][j] = DP[i-1][j] + DP[i-1][j-1] * arr[i];
    }
}
for(int i=1; i<=k; i++) ans+=DP[n][i];
coding1101
  • 183
  • 1
  • 7