# Coin Change

Coin Change is the problem of finding the number of ways of making changes for a particular amount of cents, ${\displaystyle n}$, using a given set of denominations ${\displaystyle 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 ${\displaystyle N}$ cents, and we have infinite supply of each of ${\displaystyle 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 ${\displaystyle N}$ and a set of integers ${\displaystyle S=\{S_{1},S_{2},\ldots ,S_{m}\}}$, how many ways can one express ${\displaystyle N}$ as a linear combination of ${\displaystyle S=\{S_{1},S_{2},\ldots ,S_{m}\}}$ with non-negative coefficients?

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

For example, for ${\displaystyle N=4,S=\{1,2,3\}}$, there are four solutions: ${\displaystyle \{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 ${\displaystyle N=\sum _{k=1\ldots m}{x_{k}S_{k}}}$ where ${\displaystyle x_{k}\geq 0,k\in \{1\ldots m\}}$ (Is there a solution for integer ${\displaystyle N}$ and a set of integers ${\displaystyle S=\{S_{1},S_{2},\ldots ,S_{m}\}}$?)

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

## Recursive Formulation

We are trying to count the number of distinct sets.

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

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

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

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

Thus, we can formulate the following:

${\displaystyle C(N,m)=C(N,m-1)+C(N-S_{m},m)}$

with the base cases:

• ${\displaystyle 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)
• ${\displaystyle C(N,m)=0,N<0}$ (no solution -- negative sum of money)
• ${\displaystyle 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 ${\displaystyle R(n,m). As a result, this satisfies the optimal-substructure property of dynamic programming.

The result can be computed in ${\displaystyle 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]