Coin Change

From Algorithmist

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...m]. It is a general case of Integer Partition.

[edit] Overview

The problem is defined follows:

Given an integer n, and a set of integers S={S[1],S[2],...,S[m]}.

How many ways can one express n as a linear combination of S[1..m] with non-negative coefficients?

In other words,

If we want to make change for n cents, and we have infinite supply of each of S[1..m] valued coins, how many ways can we make the change (order of coins does not matter: {1,2,1} = {1,1,2} = {2,1,1}).

For example, if n = 4, S = {1, 2, 3}:

We may have: {1,1,1,1},{1,1,2},{2,2},{1,3}.

A total of 4 ways.

[edit] Recursive formulation

We define a particular solution to the question to be a set, in the above example, {1,1,1,1} is a solution, and {2,2} is another solution, for n=4, S={1,2,3}.

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

Now, for a particular n and S[1..m] = {S[1],S[2],...,S[m]} (again, we impose that S[1]<S[2]<...<S[m], so that our solutions can be constructed in non-decreasing order), the set of solutions for this problem, P[n][m], can be partitioned:

• There are those sets that does not contain any S[m],
• and those sets that contain at least 1 S[m],

If a solution does not contain S[m], we are actually making change for n without S[m](using only S[1..m-1]), this partition are solutions of P[n][m-1].

If a solution contains S[m], then we know we are using at least 1 S[m] in our change, resulting in n-S[m] amount of cents left to be changed. Thus, this partition are solutions of P[n-S[m]][m].

In conclusion

P[n][m]=P[n][m-1]+P[n-S[m]][m].

P[n=0][m] = 1.

P[n<0][m] = 0.

P[n>=1][m<=0] = 0.

[edit] Dynamic programming

Note that the recursion satisfies the weak ordering R(n,m) < R(x,y) iff n<=x and m<=y and (n,m)!=(x,y). This as a result satisfies The optimal-substructure property of dynamic programming.

Thus, the result can be computed in O(nm) time. A good solution to this problem can be found here