Algorithms in JS: Making Change

4 min readDec 27, 2016

Problem

Given a set of coins, and an amount of change we need to return, we are asked to calculate the number of ways we can return the correct change, given our set of coins.

Note: We have an unlimited amount of each coin type at our disposal.

Building Intuition

The most naive solution we usually reach for is looping through all the different possibilities. In this case, this doesn’t seem like the best idea. First of all, the looping itself would be none trivial. We’d have to account for a lot of different situations.

Ok, this is a start. We have an idea of a solution that could work, but right away it seems messy, and not like a solution I would particularly enjoy coding out. Could we use the same approach of checking all possibilities, but with a cleaner implementation? Recursive solutions usually allow us to write more concise code. Let’s try that!

Recursive Solution

Let’s think back to our recursion workshop. How do we go about defining a recursive function?

Function definition — Our function should accept parameters. This way we can always test the value of these params to check whether or not we have reached the base case.
Defining our base case — What is the trivial case, where we already know the solution for the problem.
Make the problem smaller — Incrementing/decrementing our parameters which are passed into every recursive function call. If we don’t do this, our problem will never be terminated, and we will hit an infinite loop.

Let’s start off with thinking about our base case. What would be really easy to solve? Once we understand this, we will have a clearer understanding of how our function declaration should look like.

Handling the base cases

Case 1:

What if the amount of change we are required to return is equal to 0? This is easy, there is only 1 way to returns 0 cents. We shouldn’t return anything at all.

Case 2:

What if we have to return a certain amount of change (amount > 0), but have no coins? In this case, we should return 0, b/c we have exactly zero ways to return change.

Case 3:

What if we need to return a negative amount of change? That’s impossible! So we can return 0 in this case as well.

Our function definition

When analyzing our base case, we reached 3 simple cases which we know how to solve. All of them used the number of coins at my disposal and the amount I need to return. Also, our function should definitely accept the array of coins itself so we have something to work with :) Knowing this, we will create a function that accepts all 3 of these variables as arguments. It should look like:

function waysToReturnChangeRecursive(coins, numOfCoins, amount) {}

All in all, our problem looks like this so far:

Making the problem smaller

So we start off with a pretty large problem that we don’t know how to solve, and want to make it smaller, so that we can reach our base case (which we know how to handle), before building it back up again.

What are reasonable ways to reduce the problem, so that we could eventually hit one of our base cases? Well, we need a way to decrement the amount of coins we are currently using, and the amount we need to return as change.

We could look at our current coins, numOfCoins, amount status for every coin available to us, and make 1 of the following 2 decisions:

We decide to use the current coin. In this case we can subtract amount — currentCoin, because we have selected our current coin as part of what I will eventually return as change. Since we have an unlimited amount of each coin type at our disposal, we only change the amount of change needed to be returned.
We decide to not use the current coin. In this case we can decrement the numOfCoins, because we have chosen to not use a specific coin anymore. Notice, that here we will not update the sum.

All in all the code will look like this:

Dynamic Programming

Although our recursive solution works, it is redundant, because we end up computing a lot of the same scenarios more than once. (Think back to the drawing of the Fibonacci tree in class). Basically, we are doing a lot of unnecessary work. Can we make our solution more efficient?

What if we stored all the calculations we make, so that when the sub-problem appears again, we could check whether or not we already calculated it? If we did calculate it, we could just use that result, instead of computing more values. We would need to store all those calculations though. We could use an array! So let’s take the logic of our previous recursive implementation and combine it with our dynamic programming approach. All in all it should like:

Conclusion

First of all, if you have made it this far, congrats. This is not an easy problem. Recursion and Dynamic Programming are two algorithmic approaches which require a lot of patience and practice. The positive side though is, once it clicks you begin to notice that many of these types of problems are very similar, simply with a different back story.

Questions? You can reach me on LinkedIn, or email me at omerg@israeltechallenge.com ❤