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

numWays(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:

numWays(amount - 2) # number of ways to make change after handing them a value of 2

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

numWays(amount) = sum( # sum over all possible values
    # number of ways to make change after handing them a value of `val`
    numWays(amount - val)
    for val in values
)

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.

numWays(0) = 1
numWays(amount < 0) = 0

3. Code

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

def numWaysToSum(amount, values):
    def numWays(amount):
        # base case
        if amount < 0:
            return 0
        if amount == 0:
            return 1
        
        # recursion
        return sum(numWays(amount - val) for val in values)
    return numWays(amount)

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.

def numWaysToSum(amount, values):
    numWays = [1]*(amount+1) # array to store numWays[a]
    # automatically starts with base case numWays[0] = 1

    # recursion
    for amount in range(1, amount + 1):
        numWays[amount] = sum(
            0 if amount - val < 0 else numWays[amount - val]
            for val in values
        )
    return numWays[amount]

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

Space Complexity $O(\tt amount)$