Complete search algorithm for combinations of coins

Question

The problem is similar to coin change problem, but a little different.

The problem is stated as: You have a collection of coins, and you know the values of the coins and the quantity of each type of coin in it. You want to know how many distinct sums you can make from non-empty groupings of these coins.

So for example of coins = [1, 2, 3] and quantity = [1, 2, 2], there are 11 possible sums, basically all numbers from 1 - 11.

The length of the array coins can only go up to 20 but a quantity[x] can go up to 10^5.

What would be a possible algorithm solution that is efficient. Gathering all possible combinations of such a large quantity will take forever. Is there a mathematical formula that can determine the answer? I dont see how that it will work especially it wants distinct sums.

I was thinking of generating an array base on the coins and its quantity. Basically its multiple:

[ [1],
  [2, 4],
  [3, 6]]

Then have to select 1 or none from each of the arrays.

1
1,2
1,4
1,3
...
1,4,6

I cant seem to think of a good algorithm to perform that though. Doing nested loop might be too slow since there could be 20 different coins and each coin could have a large quantity.

Another possible solution is looping through 1 to maximum. Where maximum is the sum of all coins times its associated quantity. But the problem would be in determining if there exist a subset that will be equal to that number. I know there is a dynamic programming algorithm (subset sum) to determine if there exists a subset that will add up to a certain value, but what would be the array?

For this example it works fine, having the list as [1,2,4,3,6] and target sum is 11 then count the 'True' in DP will get 11. But for example coins = [10,50,100] and quantity = [1,2,1]. The answer is 9 possible sum but if using subset sum DP algo will get 21 'True'. If the list provided was [10,50,100,100] or [10,50,100] base on [[10], [50, 100], [100]]

A python solution would be preferred, but not necessary.

Below is my current code which got 21 for the [10,50,100] coins example.

def possibleSums(coins, quantity):
    def subsetSum(arr,s):
        dp = [False] * (s + 1)  
        dp[0] = True

        for num in sorted(arr):  
            for i in range(1, len(dp)):  
                if num <= i:  
                    dp[i] = dp[i] or dp[i - num]  
        return sum(dp)


    maximum = sum((map(lambda t: t[0] * t[1], zip(coins, quantity))))

    combinations = [[]]*len(coins)
    for i,c in enumerate(coins):
        combinations[i] = [ j for j in range(c,(c*quantity[i])+1,c) ]

    array = []
    for item in combinations:
        array.extend(item)

    print(subsetSum(array,maximum) - 1)

Guaranteed constraints:

1 ≤ coins.length ≤ 20,
1 ≤ coins[i] ≤ 10^4.

quantity.length = coins.length,
1 ≤ quantity[i] ≤ 10^5.

It is guaranteed that (quantity[0] + 1) * (quantity[1] + 1) * ... * (quantity[quantity.length - 1] + 1) <= 10^6.

Answer 1

Bug fix

Your original solution is fine, except that you need to iterate in reverse order to avoid being able to keep adding the same coin multiple times.

Simply change the inner loop to:

    for num in sorted(arr):  
        for i in range(len(dp)-1,-1,-1):  
            if num <= i:  
                dp[i] = dp[i] or dp[i - num]

More efficient solution

You can also reduce the complexity by taking advantage of the multiple coins with the same value by scanning up each possible remainder in turn:

def possibleSums2(coins, quantity):
    maximum = sum((map(lambda t: t[0] * t[1], zip(coins, quantity))))

    dp = [False] * (maximum + 1)
    dp[0] = True
    for coin,q in zip(coins,quantity):
        for b in range(coin):
            num = -1
            for i in range(b,maximum+1,coin):
                if dp[i]:
                    num = 0
                elif num>=0:
                    num += 1
                dp[i] = 0 <= num <= q

    print(sum(dp) - 1)

This will have complexity O(maximum * coins) instead of O(maximum * coins * quantity)