Recursion

Coin Change Ways

You're running a cash register and need to make change for a certain amount amount. You can only use certain denominations of coins, which are given in the array values. For example, you might only have 3 dollar coins and 9 dollar coins.

Return the total number of ways you can hand customers change for the given amount.

Example:

\notag \begin{align*} &\large \texttt{amount = 4}\\ &\large \texttt{values = [1, 2]} \\[10 bp] &\large \texttt{=> returns 5} \\ \end{align*}

Explanation: There are 5 ways you can hand the customer their change. They are $(\texttt{1+1+1+1})$ , $(\texttt{2+1+1})$ , $(\texttt{1+2+1})$ , $(\texttt{1+1+2})$ , and $(\texttt{2+2})$ .

First Few Test Cases:

To solve this problem, we want to find the number of ways to hand the customer change for the given amount.

1. Recursion

In order to make change for an amount you need to hand the customer one of the values that's available to you in the values array. For example, you might hand the customer a 2 dollar coin. You can find the number of ways to hand them a 2 dollar coin like this:

To find the recursion, you have to sum over all possible ways of handing the customer their change:

2. Base case

The recursion will call itself on smaller and smaller amounts, until it eventually reaches 0 and even negative amounts. There are no ways to make change for a negative amount, and there's only 1 way to get to the amount 0, since we always start with it.

3. Code

We could naively code this up (spoiler below), but this recursion has many redundant calls.

This means we need to use Dynamic Programming to optimize. numWays(amount) only depends on numWays(smaller amounts), so we can compute numWays on smaller amounts first and bigger ones last. This is called "Tabulation". We'll take care of the numWays(amount < 0) base case in the sum, since it's not really possible to take care of anywhere else.

Time Complexity $O(\tt amount\cdot |\texttt{values}|)$

Space Complexity $O(\tt amount)$

Mark as Completed:

Submits:

numWaysToSum

Test your code to get an output here!

numWaysToSum(

)

Test your code to get an output here!