Coin Change

From Algorithmist
Jump to: navigation, search

Coin Change is the problem of finding the number of ways of making changes for a particular amount of cents, n, using a given set of denominations d_{1}\ldots d_{m}. It is a general case of Integer Partition, and can be solved with dynamic programming. (The Min-Coin Change is a common variation of this problem.)


The problem is typically asked as: If we want to make change for N cents, and we have infinite supply of each of S=\{S_{1},S_{2},\ldots ,S_{m}\} valued coins, how many ways can we make the change? (For simplicity's sake, the order does not matter.)

It is more precisely defined as:

Given an integer N and a set of integers S=\{S_{1},S_{2},\ldots ,S_{m}\}, how many ways can one express N as a linear combination of S=\{S_{1},S_{2},\ldots ,S_{m}\} with non-negative coefficients?

Mathematically, how many solutions are there to N=\sum _{{k=1\ldots m}}{x_{k}S_{k}} where x_{k}\geq 0,k\in \{1\ldots m\}

For example, for N=4,S=\{1,2,3\}, there are four solutions: \{1,1,1,1\},\{1,1,2\},\{2,2\},\{1,3\}.

Other common variations on the problem include decision-based question, such as:

Is there a solution for N=\sum _{{k=1\ldots m}}{x_{k}S_{k}} where x_{k}\geq 0,k\in \{1\ldots m\} (Is there a solution for integer N and a set of integers S=\{S_{1},S_{2},\ldots ,S_{m}\}?)

Is there a solution for N=\sum _{{k=1\ldots m}}{x_{k}S_{k}} where x_{k}\geq 0,k\in \{1\ldots m\},\sum _{{k=1\ldots m}}{x_{k}}\leq T (Is there a solution for integer N and a set of integers S=\{S_{1},S_{2},\ldots ,S_{m}\} such that \sum _{{k=1\ldots m}}{x_{k}}\leq T - using at most T coins)

Recursive Formulation[edit]

We are trying to count the number of distinct sets.

The set of solutions for this problem, C(N,m), can be partitioned into two sets:

  • There are those sets that do not contain any S_{m} and
  • Those sets that contain at least 1 S_{m}

If a solution does not contain S_{m}, then we can solve the subproblem of N with S=\{S_{1},S_{2},\ldots ,S_{{m-1}}\}, or the solutions of C(N,m-1).

If a solution does contain S_{m}, then we are using at least one S_{m}, thus we are now solving the subproblem of N-S_{m}, S=\{S_{1},S_{2},\ldots ,S_{m}\}. This is C(N-S_{m},m).

Thus, we can formulate the following:


with the base cases:

  • C(N,m)=1,N=0 (one solution -- we have no money, exactly one way to solve the problem - by choosing no coin change, or, more precisely, to choose coin change of 0)
  • C(N,m)=0,N<0 (no solution -- negative sum of money)
  • C(N,m)=0,N\geq 1,m\leq 0 (no solution -- we have money, but no change available)


def count( n, m ):
    if n < 0 or m <= 0: #m < 0 for zero indexed programming languages
        return 0
    if n == 0: # needs be checked after n & m, as if n = 0 and m < 0 then it would return 1, which should not be the case.
        return 1
    return count( n, m - 1 ) + count( n - S[m], m )

Dynamic Programming[edit]

Note that the recursion satisfies the weak ordering R(n,m)<R(x,y)\iff n\leq x,m\leq y,(n,m)\neq (x,y). As a result, this satisfies the optimal-substructure property of dynamic programming.

The result can be computed in O(nm) time - the above pseudocode can easily be modified to contain memoization. It can be also rewritten as:

func count( n, m )

  for i from 0 to n
    for j from 0 to m
      if i equals 0
         table[i, j] = 1          
      else if j equals 0
         table[i, j] = 1 if i%S[j] equals 0 else 0
      else if S_j greater than i
         table[i, j] = table[i, j - 1]
         table[i, j] = table[i - S_j, j] + table[i, j-1]

  return table[n, m]