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.

visitAll(currCoins, total, idx)

1. Recursion

We can generate solutions like this:

solns = []

visitAll(currCoins, total, idx) = (

    # add current coin's value again

    visitAll(currCoins + [values[idx]], total + values[idx], idx)

    # move on to the next coin

    visitAll(currCoins, total, idx+1)
)

2. Base case

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

if total == amount:
    solns.append(currCoins) # add to our solutions
    return

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

if total > amount or idx == len(values):
    return

3. Code

Here's the recursive code:

def allCashRegisterOptions(values, amount):
    solns = []

    def visitAll(currCoins, total, idx):
        # base case
        if total > amount or idx == len(values):
            return
        if total == amount:
            solns.append(currCoins)
            return

        # recursion
        visitAll(currCoins + [values[idx]], total + values[idx], idx)

        visitAll(currCoins, total, idx+1)

    visitAll(0, [], 0)
    return solns

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

def allCashRegisterOptions(amount, nums):
    # global parameters
    numbers = []
    idx = 0 
    total = 0

    solns = []


    def visitAll():
        # without `nonlocal` we'd just be setting local variables
        nonlocal numbers, idx, total, solns

        # base case
        if total > amount or idx == len(nums):
            return
        # recursion
        if total == amount:
            solns.append(numbers.copy())
            return

        numbers.append(nums[idx])
        total += nums[idx]
        visitAll()
        total -= nums[idx]
        numbers.pop()

        idx += 1
        visitAll()
        idx -= 1

    visitAll()
    return solns

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.