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.

Since order does not matter, we will impose that our solutions (sets) are all sorted in non-decreasing order (Thus, we are looking at sorted-set solutions: collections).

For a particular $N$ and $S=\{S_{1},S_{2},\ldots ,S_{m}\}$ (now with the restriction that $S_{1}, our solutions can be constructed in non-decreasing order), 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:
return 1
if n < 0:
return 0
if m <= 0 and n >= 1: #m < 0 for zero indexed programming languages
return 0

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
for j from 0 to m
if i equals 0
table[i, j] = 1
else if j equals 0
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]