# Coin counting

#### Posted on February 28, 2013

##### Last updated on March 6, 2013

Problem Statement:

Assuming you have an infinite supply of coins of various denominations, in how many ways can you make change for a certain amount of money? Formally, given a set $$S$$ of $$m$$ positive integers and a positive integer $$N$$, how many distinct solutions are there to the equation $$\sum_{i=1}^m V_i S_i = N$$ where $$V_i$$ is an integer greater than 0.

Let’s look at a simple example. Assuming you have cent coins [1,2,5], and want to make change for $$5$$ cents, you can do that in $$4$$ ways, mainly:

Let’s deconstruct the problem into these facts:

• Given an element $$S_i$$ from $$S$$, any solution must either exclude $$S_i$$, or include at least one $$S_i$$.
• To make $$0$$, regardless of $$S$$, there is only one solution, the empty solution.
• If $$N < 0$$, there are no solutions
• If $$S = \{\}$$, and $$N > 0$$, there are no solutions.

Since it might be useful, in the following code snippet, we not only count all the possibilities, but also output them.

Notice that the above solution also has memoization.

Let’s try this out on making change on a 2 pound coin, using all the coins, ie $$S=\{200,100,50,20,10,5,2,1\}$$.

We get the correct answer of $$73682$$.

Notice that we can use this to solve the solve the unordered integer partition problem.

Let’s try it out to find all the possible integer partitions of $$5$$.

Code available as a gist

Markdown SHA1: 56750d13d01554e24f3fb7849281a7935d07e610