Change coins in Python with recursive / Why no work?

Question

this my code. The task of changing coins. I need to get a list of lists, with exchange options.

a = []
def coinChange(coins, amount, result=None):
    if result is None: 
        result = []
    
    if amount < 1 and sum(result) == 3:
        return a.append(result)

    else:
        for i in coins:
            if amount - i >= 0:
                result.append(i)
                coinChange(coins, amount - i, result)            
    return 

coinChange([1,2,3], 3)
print(a)

They return

[1,1,1,2,2,1,3]

But I need to get a list of lists. Each sublist should contain only those numbers that add up to 3.

For Example:

[[1,1,1], [2,1], [3]]

How do i get such a list? thank

Answer 1

I would even take DarrylG's answer further and advise against passing results through the recursion stack, as it complicates the whole idea of recursions.

Simply put, you should usually:

1. Assume you can solve a smaller version of your problem (which is the exact function you are implementing)
2. Solve the original problem using the solutions of the smaller problems (the recursive step, here you call the function)
3. Define an explicit solution for the simplest case you have for your problem, which is essentially the recursion's stopping condition.

Here is an example code for solving the problem with these tips:

def coinChange(coins, sum):
    # Stop condition.
    if sum == 0:
        return [[]]

    # Recursive step
    solutions = []
    for i, coin in enumerate(coins):
        if coin <= sum:
            lst = coinChange(coins[i:], sum - coin)
            solutions.extend([[coin] + l for l in lst])

    return solutions


print(coinChange([1, 2, 3], 3))

result of running:

[[1, 1, 1], [1, 2], [3]]

nice test for checking if you did these steps without dependency is trying to one-line your code:

def coinChange(coins, sum):
    return [[c] + l for i, c in enumerate(coins) if c <= sum for l in coinChange(coins[i:], sum - c)] if sum > 0 else [[]]

note that sometimes it might be unreadable, so it's your decision weather to keep it in one-line form.

Answer 2

Simple solution

Code

def coinChange(coins, amount, result=None, solutions = None):
    '''
        result - stores current set of coins being tries
        soltions - solutions found so far
    '''
    if result is None: 
        result = []
        
    if solutions is None:
        solutions = []

    if amount == 0:
        # Add solution
        solutions.append(result[:])  # append a copy since result will change
    elif amount > 0:
        for i in coins:
            if amount - i >= 0:
                # Adding i to list of coins to try
                coinChange(coins, amount - i, result + [i,], solutions)
                
    return solutions
            

Test

a = coinChange([1,2,3], 3)
print(a)
            
# Capture the solution in a (i.e. don't make it global--generally bad practice)         
a = coinChange([1,2,3], 3)
print(a)

Output

[[1, 1, 1], [1, 2], [2, 1], [3]]

Even Simpler Using Generators

def coinChange(coins, amount, result=None):
    '''
        result - stores current set of coins being tries
        soltions - solutions found so far
    '''
    if result is None: 
        result = []
        
    if amount == 0:
        # report solution
        yield result
        
    if amount > 0:
        for i in coins:
            yield from coinChange(coins, amount - i, result + [i,])    
            
a = list(coinChange([1,2,3], 3))
print(a)

Using Cache

Easiest to illustrate use of cache by modifying GalSuchetzky answer.

Issue

• Can't directly use cache on coinChange function since arguments are not hashable (e.g. coins is a list, so not hashable)
• We get back this by using a nested function (helper) whose arguments are hashable that indexes into coins as necessary

Code

def coinChange(coins, sum_):
    '''
        Inputs:
            coins - list of coins
            sum_  - value coin should sum to (use sum_ since sum is a builtin function)
    '''
    
    def coinChangeHelper(j, total):
        '''
            Uses cache to compute solutions
            
            Need helper function since coins is a list so can't be hashed to placed in cache
            
            Inputs:
                j     - current index into coins
                total - current sum
        '''
        if (j, total) in mem_cache:
            # Use cache value
            return mem_cache[(j, total)]
        
        # Stop condition.
        if total == 0:
            mem_cache[(j, total)] = [[]]
        else:
            # Recursive step
            solutions = []

            for i in range(j, len(coins)):
                if coins[i] <= total:
                    lst = coinChangeHelper(i, total - coins[i])
                    solutions.extend([[coins[i]] + l for l in lst])

            mem_cache[(j, total)] = solutions
        
        return mem_cache[(j, total)]

    # Init cache
    mem_cache = {}
    
    return coinChangeHelper(0, sum_)

print(coinChange([1, 2, 3], 3))