20

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.

3
  • This feels like it might be NP-hard. I suspect there's a way to reduce some variant of the partition problem to this problem. Commented Apr 26, 2017 at 18:50
  • Is there any limit on coin values? Commented Apr 26, 2017 at 18:54
  • I updated the question with the limit/constraints. I forgot to mention that this is a problem from codefights with about 100 people who solved it. So theres definitely a solution that can solve it in 4 secs (python) or 0.5 (c++) Commented Apr 26, 2017 at 18:58

10 Answers 10

13

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)

13
  • Thanks for fixing the bug. This algo is the fastest. With coins = [10,50,100] and quantity = [100,2000,1000]. These are the execution times for the 3 solutions i got from here: Prune: 1.3836107661727957 (granted my code base on his explanation could possibly be optimized). Tim Peters: 43.38692857611791. Peter de Rivaz: 0.08758417620116177 Commented Apr 26, 2017 at 19:40
  • 1
    @user1179317: Your test data violates the constraints set out in the problem; there are over 10^8 possible coin combos in that test, over the 10^6 limit. Commented Apr 26, 2017 at 19:48
  • 1
    What runs fastest depends heavily on how the maximum sum compares to the number of possible coin combinations, and (for some possible solutions, including some versions of the polynomial multiplication idea) how many duplicate sums there are. This solution is good for a maximum sum lower than the number of possible coin combos; for a maximum higher than the number of possible coin combos, other solutions are likely to perform better. Commented Apr 26, 2017 at 19:48
  • 1
    @ScottSkiles dp[i] is true if and only if value i can be made from the coins Commented Jun 26, 2017 at 6:53
  • 1
    @black.swordsman That constraint is not for the maximum sum, but for the total number of different combinations, so it gives an upper bound for the answer (which is counting the number of distinct sums) Commented Sep 3, 2022 at 11:10
12

Don't gather all the combinations, just the sums.

Your set of sums starts with [0]. Cycle through the coins, one at a time. For each coin, iterate through its quantity, adding that multiple to each item of the set. Set-add each of these sums to the set. For example, let's take that original case: coins = [1, 2, 3], quant = [1, 2, 2]. Walking through this ...

sum_set = {0}
current_coin  = 1;  #  coin[0]
current_quant = 1;  # quant[0]
This step is trivial ... add 1 to each element of the set.  This gives you {1}.
Add that to the existing set.  You now have
sum_set = {0, 1}

Next coin:

current_coin  = 2;  #  coin[0]
current_quant = 2;  # quant[0]
Now, you have two items to add to each set element: 1*2, giving you {2, 3}; and 2*2, giving you {4, 5}.  
Add these to the original set:
sum_set = {0, 1, 2, 3, 4, 5}

Final coin:

current_coin  = 3;  #  coin[0]
current_quant = 2;  # quant[0]
You add 1*3 and 2*3 to each set element, giving you {3, 4, 5, 6, 7, 8} and {6, 7, 8, 9, 10, 11}.  
Adding these to the sum_set gives you the set of integers 0 through 11.

Remove 0 from the set (since we're not interested in that sum) and take the size of the remaining set. 11 is your answer.

Is that enough to let you turn this into an algorithm? I'll leave the various efficiencies up to you.

6
  • This seems like a simple, yet smart solution. Let me try it out Commented Apr 26, 2017 at 19:06
  • Great! When you get to a resolution, please remember to up-vote useful things and accept your favourite answer (even if you have to write it yourself), so Stack Overflow can properly archive the question.
    – Prune
    Commented Apr 26, 2017 at 19:24
  • Had to pick Tim Peters answer, it was the fastest. Your answer is still nice and simple though :P Commented Apr 26, 2017 at 19:41
  • @user1179317: I think you may have gotten your Peters mixed up. Commented Apr 26, 2017 at 19:42
  • Oh my bad, i did. I meant Peter de Rivaz Commented Apr 26, 2017 at 20:10
4

I was going to put up a solution using generating functions, but then you added

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

In that case, just brute force it! Go through every possible set of coins, compute the sum, and use a set to find how many unique sums you get. 10^6 possibilities is trivial.


As for the generating function solution, we can represent the sums possible with a quantity Q of coins of value V through the polynomial

1 + x^V + x^(2V) + ... + x^(QV)

where a term with exponent N means a sum of value N can be achieved.

If we then multiply two polynomials, for example

(1 + x^(V1) + x^(2*V1) + ... + x^(Q1*V1))(1 + x^(V2) + x^(2*V2) + ... + x^(Q2*V2))

the presence of a term with exponent N in the product means that a sum of value N can be achieved by combining the coins corresponding to the input polynomials.

Efficiency then comes down to how we multiply polynomials. If we use dicts or sets to efficiently look up terms by exponent, we can win over brute force by combining like terms to eliminate some of the redundant work brute force does. We can discard the coefficients, since we don't need them. Advanced polynomial multiplication algorithms based on a number-theoretic transform may give further savings in some cases.

3
  • Yea i just noticed that too when i copied it from the site. It's a lot smaller than i thought. You should put up the solution you were thinking of anyways, im still interested :P Commented Apr 26, 2017 at 19:04
  • @user1179317: I've added some elaboration on generating functions. Commented Apr 26, 2017 at 19:34
  • Thanks for the explanation. This seems quite too complicated for me hehe. Thanks though Commented Apr 26, 2017 at 19:45
3

Here's a concise brute-force solution (Python 3):

def numsums(values, counts):
    from itertools import product
    choices = [range(0, v*c+1, v) for v, c in zip(values, counts)]
    sums = {sum(p) for p in product(*choices)}
    return len(sums) - 1  # sum "0" isn't interesting

Then, e.g.,

print(numsums([10,50,100], [1, 2, 1])) # 9
print(numsums([1, 2, 3], [1, 2, 2])) # 11
print(numsums([1, 2, 4, 8, 16, 32], [1]*6)) # 63

Eliminating duplicates along the way

This variation is functionally equivalent to some other answers; it's just showing how to do it as a variation of the brute-force way:

def numsums(values, counts):
    sums = {0}
    for v, c in zip(values, counts):
        sums |= {i + choice
                 for choice in range(v, v*c+1, v)
                 for i in sums}
    return len(sums) - 1  # sum "0" isn't interesting

In fact, if you squint just right ;-) , you can view it as one way of implementing @user2357112's polynomial multiplication idea, where "multiplication" has been redefined just to keep track of "is a term with this exponent present or not?" ("yes" if and only if the exponent is in the sums set). Then the outer loop is "multiplying" the polynomial so far by the polynomial corresponding to the current (value, count) pair, and the multiplication by the x**0 term is implicit in the |= union. Although, ya, it's easier to understand if you skip that "explanation" ;-)

3
  • Thanks, this solution works but I think it'll go over the time limit. Solution mentioned by @prune was much faster Commented Apr 26, 2017 at 19:30
  • As @user2357112 noted, there are no more than a million elements in the product - by modern standards, that's tiny ;-)
    – Tim Peters
    Commented Apr 26, 2017 at 19:31
  • True. I tested the 3 solutions i got and will post the execution times just for reference for anybody in the future. Commented Apr 26, 2017 at 19:35
2

This is one is even more optimized

function possibleSums(coins, quantity) {
  // calculate running max sums
  var max = coins.reduce(function(s, c, i) {
    s += c * quantity[i];
    return s;
  }, 0);

  var sums = [0];
  var seen = new Map();

  for (var j = 0; j < coins.length; j++) {
    var coin = coins[j];
    var n = sums.length;
    for (var i = 0; i < n; i++) {
      var s = sums[i];
      for (var k = 0; k < quantity[j]; k++) {
        s += coin;
        if (max < s) break;
        if (!seen.has(s)) {
          seen.set(s, true);
          sums.push(s);
        }
      }
    }
  }
  return Array.from(seen.keys()).length;
}
1

Easy python solution

Note:using dynamic programming and finding all sums may result in time limit exceed.

def possibleSums(coins, quantity):
    combinations = {0}
    for c,q in zip(coins, quantity):
        combinations = {j+i*c for j in combinations for i in range(q+1)}
    
    return len(combinations)-1
0

hmm. it's very interesting problem. If you want to just get the sum value use possibleSums(). To view all cases, use possibleCases().

import itertools


coins = ['10', '50', '100']
quantity = [1, 2, 1]

# coins = ['A', 'B', 'C', 'D']
# quantity = [1, 2, 2, 1]


def possibleSums(coins, quantity):
    totalcnt=1
    for i in quantity:
        totalcnt = totalcnt * (i+1)
    return totalcnt-1    # empty case remove


def possibleCases(coins, quantity):
    coinlist = []
    for i in range(len(coins)):
        cset=[]
        for j in range(quantity[i]+1):
            val = [coins[i]] * j
            cset.append(val)
        coinlist.append(cset)
    print('coinlist=', coinlist)

    # combination the coinlist
    # cases=combcase(coinlist)
    # return cases
    alllist =  list(itertools.product(*coinlist))
    caselist = []
    for x in alllist:
        mergelist = list(itertools.chain(*x))
        if len(mergelist)==0 :  # skip empty select.
            continue
        caselist.append(mergelist)
    return caselist


sum = possibleSums(coins, quantity)
print( 'sum=', sum)

cases = possibleCases(coins, quantity)
cases.sort(key=len, reverse=True)
cases.reverse()

print('count=', len(cases))
for i, x in enumerate(cases):
    print('case',(i+1), x)

output is this

sum= 11
coinlist= [[[], ['10']], [[], ['50'], ['50', '50']], [[], ['100']]]
count= 11
case 1 ['10']
case 2 ['50']
case 3 ['100']
case 4 ['10', '50']
case 5 ['10', '100']
case 6 ['50', '50']
case 7 ['50', '100']
case 8 ['10', '50', '50']
case 9 ['10', '50', '100']
case 10 ['50', '50', '100']
case 11 ['10', '50', '50', '100']

you can test other cases. coins = ['A', 'B', 'C', 'D'] quantity = [1, 3, 2, 1]

sum= 47
coinlist= [[[], ['A']], [[], ['B'], ['B', 'B'], ['B', 'B', 'B']], [[], ['C'], ['C', 'C']], [[], ['D']]]
count= 47
case 1 ['A']
case 2 ['B']
case 3 ['C']
case 4 ['D']
case 5 ['A', 'B']
case 6 ['A', 'C']
case 7 ['A', 'D']
case 8 ['B', 'B']
case 9 ['B', 'C']
case 10 ['B', 'D']
case 11 ['C', 'C']
case 12 ['C', 'D']
case 13 ['A', 'B', 'B']
case 14 ['A', 'B', 'C']
case 15 ['A', 'B', 'D']
case 16 ['A', 'C', 'C']
case 17 ['A', 'C', 'D']
case 18 ['B', 'B', 'B']
case 19 ['B', 'B', 'C']
case 20 ['B', 'B', 'D']
case 21 ['B', 'C', 'C']
case 22 ['B', 'C', 'D']
case 23 ['C', 'C', 'D']
case 24 ['A', 'B', 'B', 'B']
case 25 ['A', 'B', 'B', 'C']
case 26 ['A', 'B', 'B', 'D']
case 27 ['A', 'B', 'C', 'C']
case 28 ['A', 'B', 'C', 'D']
case 29 ['A', 'C', 'C', 'D']
case 30 ['B', 'B', 'B', 'C']
case 31 ['B', 'B', 'B', 'D']
case 32 ['B', 'B', 'C', 'C']
case 33 ['B', 'B', 'C', 'D']
case 34 ['B', 'C', 'C', 'D']
case 35 ['A', 'B', 'B', 'B', 'C']
case 36 ['A', 'B', 'B', 'B', 'D']
case 37 ['A', 'B', 'B', 'C', 'C']
case 38 ['A', 'B', 'B', 'C', 'D']
case 39 ['A', 'B', 'C', 'C', 'D']
case 40 ['B', 'B', 'B', 'C', 'C']
case 41 ['B', 'B', 'B', 'C', 'D']
case 42 ['B', 'B', 'C', 'C', 'D']
case 43 ['A', 'B', 'B', 'B', 'C', 'C']
case 44 ['A', 'B', 'B', 'B', 'C', 'D']
case 45 ['A', 'B', 'B', 'C', 'C', 'D']
case 46 ['B', 'B', 'B', 'C', 'C', 'D']
case 47 ['A', 'B', 'B', 'B', 'C', 'C', 'D']
0

This is a javascript version of Peter de Rives but a little more efficient since it does not have to do maximum iteration for each coin to find its remainder



function possibleSums(coins, quantity) {
    // calculate running max sums
  var prevmax = 0;
  var maxs = [];
  for (var i = 0; i < coins.length; i++) {
    maxs[i] = prevmax + coins[i] * quantity[i];
    prevmax = maxs[i];
  }

  var dp = [true];

  for (var i = 0; i < coins.length; i++) {
    var max = maxs[i];
    var coin = coins[i];
    var qty = quantity[i];
    for (var j = 0; j < coin; j++) {
      var num = -1;
      // only find remainders in range 0 to maxs[i];
      for (var k = j; k <= max; k += coin) {
        if (dp[k]) {
          num = 0;
        } 
        else if (num >= 0) {
          num++;
        }
        dp[k] = 0 <= num && num <= qty;    
      }
    }
  }

  return dp.filter(e => e).length - 1;
}

0
def possibleSums(coins, quantity) -> int:
    from itertools import combinations

    flat_list = []
    for coin, q in zip(coins, quantity):
        flat_list += [coin]*q

    uniq_sums = set([])
    for i in range(1, len(flat_list)+1):
        for c in combinations(flat_list, i):
            uniq_sums.add(sum(c))

    return len(uniq_sums)
0

Translating jumarov's code to Python gives the following:

def possibleSums4(coins, quantity=None):
    if quantity is None:
        coins, quantity = zip(*coins.items())
    max = sum(i*j for i,j in zip(coins, quantity))
    dp = {0}
    for c, q in zip(coins, quantity):
        for b in range(c):
            num = -1
            for i in range(b, max + 1, c):
                if i in dp:
                    num = 0
                elif num >= 0:
                    num += 1
                    if 0 <= num <= q:
                        dp.add(i)
    return(len(dp) - 1)

What interests me about this is that for a given set of coins it looks like once they all reach a certain multiplicity, the behavior of the number of sub-sums becomes very regular: the addition of another coin introduces an increase in the number of possible sums by the value of the coin.

Consider the coin set {4, 5, 7}. When each is used at most once, the possible sums are {0, 4, 5, 7, 9, 11, 12, 16}. When used up to twice there are 25 possibilities:

25: 0; 4-5; 7-25; 27-28; 32

If any more coins are added, the possibilities increases by the value of the coin(s) added. Here I use a couple of routines to help in displaying the values (which can be confirmed with other routines presented in answers of this question):

>>> show(Set(4,5,7)**2*Set(4))  # Set(1,2)**2 -> exponents in ((1+x)*(1+x^2))^2
'29: 0; 4-5; 7-29; 31-32; 36'
>>> show(Set(4,5,7)**2*Set(5))
'30: 0; 4-5; 7-30; 32-33; 37'
>>> show(Set(4,5,7)**2*Set(7))
'32: 0; 4-5; 7-32; 34-35; 39'
>>> show(Set(4,5,7)**2*Set(4,5,7))
'41: 0; 4-5; 7-41; 43-44; 48'

Notice that the first number is higher than 25 -- the sums present at multiplicity of 2 when the structure of the sums becomes "stable" -- by the value of the coin(s) added. e.g. adding 1 more of each (4, 5, 7 which sum to 16) give a total of 25 + 16 sums possible. By "stable" I mean that the basic range of sums is fixed, only the number in the ranges varies. e.g. in this case, the structure at (and after) a multiplicity of 2 is "singleton, range of 2, varying range, range of 2, singleton" -- symmetric.

Not every set will become stable so quickly, however. Though even large sets of "coin" denominations may become so, too: the following 42 denominations give 10366 possible sums when the multiplicity is 5:

{3, 4, 5, 9, 16, 18, 20, 21, 23, 24, 25, 29, 31, 33, 34, 38, 39, 44,
47, 49, 50, 52, 55, 56, 57, 60, 61, 63, 64, 65, 68, 69, 70, 75, 78,
80, 81, 85, 88, 94, 95, 96}

With a sum of 2074, the number of sums increases by 2074 as the multiplicity of each is increased by 1. So if each coin is used 10 more times (above the stable 5), the number of sums is 10366 + 10*2074 = 31106.

The small set of coins {18, 93, 100} gives 4886 unique sums at multiplicity 26, a significantly larger multiplicity than 5 is needed to achieve stability.

So is there a formula? I don't know how to predict the number of sums when coins are used at sub-stable counts (i.e. less than the number needed to get the number of possible sums increasing in a predictable way) and I don't know how to predict when the structure will become stable (though, for two coins, it seems to be at a value 1 less than the largest coin value). But once any coins are used more than the stable multiplicity value -- a function of the coins in use -- the number of sums (and the actually sums) appear to be easy to predict.

Of course this all applies to determining which exponents are present when a polynomial with positive coefficients is raised to some power. What is special about the "coin polynomial" is that it is a product of binomials (1+x^c_1)^n_1*...*(1 + x^c_n)^m_n where coin values are c_i and multiplicities are n_i. The "stable multiplicity" is seeking the exponent m for ((1+x^c_1)*...*(1 + x^c_n))^m which gives a predictable structure for the exponents that are present when any coin has a multiplicity greater than m.

1
  • cross posting a question here
    – smichr
    Commented Jun 7, 2022 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.