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

## Contents |

## [edit] Overview

The problem is typically asked as:
If we want to make change for *N* cents, and we have infinite supply of each of 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 , how many ways can one express *N* as a linear combination of with non-negative coefficients?

Mathematically, how many solutions are there to where

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
where
(Is there a solution for integer *N* and a set of integers ?)

Is there a solution for
where
(Is there a solution for integer *N* and a set of integers such that - using at most *T* coins)

## [edit] 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 (now with the restriction that , 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}

This partitioning will essentially break the initial problem into two subproblems:

- If
*N*<*S*_{m}(that is, a solution does**not**contain*S*_{m}), then we can solve the subproblem of*N*with , or the solutions of*C*(*N*,*m*- 1). - If (that is, a solution
*does*in fact contain*S*_{m}), then we are using at least one*S*_{m}, thus we are now solving the subproblem of*N*-*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)- (no solution -- negative sum of money)
- (no solution -- we have money, but no change available)

### [edit] 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 )

## [edit] Dynamic Programming

Note that the recursion satisfies the weak ordering . As a result, this satisfies the optimal-substructure property of dynamic programming.

The result can be computed in *O*(*n**m*) 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 ]