Coin counting

Problem Statement:

Assuming you have an infinite supply of coins of various denominations, in how many ways can you make change for a certain amount of money? Formally, given a set \(S\) of \(m\) positive integers and a positive integer \(N\), how many distinct solutions are there to the equation \(\sum_{i=1}^m V_i S_i = N\) where \(V_i\) is an integer greater than 0.

Let’s look at a simple example. Assuming you have cent coins [1,2,5], and want to make change for \(5\) cents, you can do that in \(4\) ways, mainly:

[
 [1, 1, 1, 1, 1], 
 [1, 1, 1, 2], 
 [1, 2, 2], 
 [5]
]

Let’s deconstruct the problem into these facts:

• Given an element \(S_i\) from \(S\), any solution must either exclude \(S_i\), or include at least one \(S_i\).
• To make \(0\), regardless of \(S\), there is only one solution, the empty solution.
• If \(N < 0\), there are no solutions
• If \(S = \{\}\), and \(N > 0\), there are no solutions.

Since it might be useful, in the following code snippet, we not only count all the possibilities, but also output them.

memo = dict()

# Returns a list of lists of all possibilities
def coin_count(amount,poss,curpos):
  if amount == 0:
    return [[]]
  elif amount < 0 or curpos >= len(poss):
    return []
  elif (amount,curpos) in memo: # memoized
    return memo[(amount,curpos)]

  # either use poss[0]
  out = []
  for sublist in coin_count(amount-poss[curpos], poss, curpos):
    out.append( [poss[curpos]] + sublist)

  # or don't use it
  out1 = coin_count(amount,poss,curpos+1)

  # memoize
  memo[(amount,curpos)] = out + out1

  return out + out1

Notice that the above solution also has memoization.

Let’s try this out on making change on a 2 pound coin, using all the coins, ie \(S=\{200,100,50,20,10,5,2,1\}\).

coins = [200,100,50,20,10,5,2,1]
print len(coin_count(200,coins,0))

We get the correct answer of \(73682\).

Notice that we can use this to solve the solve the unordered integer partition problem.

Let’s try it out to find all the possible integer partitions of \(5\).

[
  [1, 1, 1, 1, 1], 
  [1, 1, 1, 2], 
  [1, 1, 3],
  [1, 2, 2], 
  [1, 4], 
  [2, 3], 
  [5]
]

Code available as a gist