Coin Change

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.)

Overview

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

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:

$C(N,m)=C(N,m-1)+C(N-S_{m},m)$ 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)

Pseudocode

 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

Note that the recursion satisfies the weak ordering $R(n,m) . 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+1
for j from 0 to m
if i equals 0
table[i, j] = 1
else if j equals 0
if i%S[j] equals 0
table[i, j] = 1
else
table[i, j] = 0;
else if S[j] greater than i
table[i, j] = table[i, j - 1]
else
table[i, j] = table[i - S[j], j] + table[i, j-1]

return table[n, m-1]