Subset sum variation

Question

Given an integer n and s sets of different sizes, but with positive ascending numbers from 0 to s_i as elements. Let a good sum be defined here as a_1 + a_2 + ... + a_s = n. Count how many sums are existent, when you take for every a_i an element from it's corresponding set s_i.

I tried to generate any possible way and omit those which are omittable, i.e. when you have for example s=3, n=1 and you are given the sets s_0={0,1}, s_1={0,1,2,3}, s_2={0,1,2}, then you can omit the check for the sum 0 + 0 + a_3 since a_3 won't be able to be large enough. I've applied the dynamic programming solution for normal subset sum for each of those possible sequences, however, I get much larger results than I should and its very slow, too.

Are there any good algorithms which I can apply here?

IVlad IVlad · Accepted Answer · 2015-09-26T14:45:07

You could implement a slight variation on the classical subset sum solution, by using two dictionaries (arrays can also work, but dictionaries are nicer):

dp[i] = dictionary of sums we can obtain using the first i sets and their counts


dp[0, <elements in s[0]>] = 1
for i = 1 to s - 1:
  for each element x in dp[i - 1]:
    for each element k in s[i]:
      dp[i, x + k] += dp[i - 1, x]

Complexity will be quite large, but there's not much you can do to reduce it I think. It should work though.

You can get away with only keeping two dictionaries in memory, because you only need the current and the previous ones.

Python code:

def solve(s, n):

    dp = [dict()] * len(s)

    for k in s[0]:
        dp[0][k] = 1
    for i in range(1, len(s)):
        dp[i] = dict()
        for x in dp[i - 1]:
            for k in s[i]:
                if x + k in dp[i]:
                    dp[i][x + k] += dp[i - 1][x]
                else:
                    dp[i][x + k] = dp[i - 1][x]

    return dp[len(s) - 1][n]

print(solve([[0,1,2],[0,1,2]], 3)) # prints 2
print(solve([[0,1,2],[0,1,2,3,4],[0,1,2,3,4]], 5)) # prints 13

Subset sum variation

1 Answers