0. Problem

We'll generate all the possible ways we can make change for the amount, using a recursive function. The function needs to know the current solution we have so far, currCoins. We'll also have it record the total sum of coins we have so far total so we don't have to waste time computing it when it's needed.

We also need to make sure we don't double count the same configuration of coins twice. The trick to doing this is to keep adding the same coin value over and over again, and once we move past it we never go back to it. We can do this by keeping track of which index in values we shoud use, called idx.

1. Recursion

We can generate solutions like this:

2. Base case

When we get to the amount we want, we have a solution.

We also want to stop if total goes over amount or if we go past the last possible index.

3. Code

Here's the recursive code:

It's slow to do $\texttt{currCoins + [coins[idx]]}$ since it creates a whole new array. This is where Backtracking comes in. Backtracking is when we make currCoins global so we never create a new array. We'll also make idx and amount global to go full force with Backtracking (but this doesn't affect the time or space complexity).

Time Complexity $O(\tt{amount} \cdot \texttt{v}^{\tt amount})$, where $\texttt{v}$ is the length of values. We need to build all $\texttt{v}^{\texttt{amount}}$ possibilities, and each has up to $\texttt{amount}$ entries in it.

Space Complexity $O(\tt{amount} \cdot \texttt{v}^{\tt amount})$ for the output array. The Call Stack and the global parameters also use up some space, but the output array's space complexity beats them by far.

Call Stack Complexity $O(\texttt{amount})$. The Call Stack gets $O(\texttt{amount})$ calls deep, and each call uses $O(1)$ space.