CODEWITHSUNDEEP
algorithmcombinatorics
mitchus
mitchus

Reputation: 4877

Number of constant-sum combinations

Suppose you are given n lists of integers L1,L2,...,Ln and an integer S.

I am looking for a way to efficiently count the combinations of indexes j1,j2,...,jn such that L1[j1]+L2[j2]+...+Ln[jn] = S.

As an example, take L1=[0,1,1,2], L2=[0,1], L3=[0,1,2,3,3] and S=4. Then the possible combinations are

0+1+3
0+1+3
1+0+3
1+0+3
1+1+2
1+0+3
1+0+3
1+1+2
2+0+2
2+1+1

i.e. the answer I am looking for is 10.

Upvotes: 1

Views: 465

Answers (2)

ElKamina
ElKamina

Reputation: 7817

You can solve it with DP. Complexity: O(nS).

Count(i,s) = \sum_j=0..s Count(i-1,j) * Number of elements in list i with value (s-j)

Upvotes: 1

hugomg
hugomg

Reputation: 69964

This problem is NP complete. You can

1) Brute force it

or, if you have some extra properties (the total sums involved are small, for example) you can also consider

2) Use dynamic programming to get a pseudopolinomial algorithm.

Upvotes: 2

Related Questions