CODEWITHSUNDEEP
pythonalgorithmdebugging
Adam
Adam

Reputation: 10016

Make change for n dollars with m coins

I'm trying to implement a solution to the following problem:

Given a number of dollars, n, and a list of dollar values for m distinct coins, find and print the number of different ways you can make change for n dollars if each coin is available in an infinite quantity.

The complete problem statement is here

Before presenting my solution, I should say that I know dynamic programming is probably the optimal way to solve this problem. The solution I've come up with does not use dynamic programming, and I know it is far from the most efficient solution out there. However, as far as I can tell it is correct.

The problem is that my solution underestimates the number of ways to make change. For example given n = 75 and {25 10 11 29 49 31 33 39 12 36 40 22 21 16 37 8 18 4 27 17 26 32 6 38 2 30 34} as coin values, the solution returns 182 when it should return 16694. It seems to work for smaller test cases, though.

def make_change(coins, n):    
    solns = 0
    num_coins = len(coins)
    for i in range(num_coins):
        solns = solns + make_change_rec(coins, n-coins[0], coins[0])
        
        # We've found all solutions involving coin. Remove it
        # from consideration
        coins.pop(0)
    
    return solns

def make_change_rec(coins, n, parent):
    # If n == 0 we've found a solution
    if n == 0:
        return 1
    
    solns = 0
    # For each coin
    for coin in coins:
        # If coin > n, can't make change using coin
        if coin > n or coin < parent: # coin < parent rule ensures we don't count same solution twice
            continue
            
        # Use the coin to make change 
        solns = solns + make_change_rec(coins, n-coin, coin)
        
    return solns

Can someone help me understand what I'm doing wrong? I'm using Python 3.

Upvotes: 1

Views: 480

Answers (2)

Christian Sloper
Christian Sloper

Reputation: 7510

You need to sort your coins before you input them. If your recursion runs slow for larger values (which it will) you can add memoization like this:

from functools import lru_cache

#leave your function as it is, but add this:
@lru_cache(maxsize=None)
def make_change_rec(coins, n, parent):

Upvotes: 2

lcastillov
lcastillov

Reputation: 2153

I think the only change you need to do is to sort the coins array. Now your recursion its going to run out of time for sure. So I recommend you to go with classic dynamic programming.

def make_change(coins, n):
    dp = [1] + [0] * n
    for coin in coins:
        for i in range(coin, n + 1):
            dp[i] += dp[i - coin]
    return dp[n]

Upvotes: 3

Related Questions