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

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