Write a program that, given the amount N to make change for and the number of types of m infinitely available coins, and a list of m coins, prints out how many different ways you can make change from the coins to STDOUT.
My intuition was, for each coin, to try that coin, and recurse on n - c where c is the value of the coin, returning 1 if I get to zero and 0 if I get below zero. I passed in the previously used coin and only recursed on coins less than or equal to the previous coin to prevent duplicates. I am confused why this approach is incorrect, and how I can correct it.
Here is my code:
def calc_change(n, coins):
cache = {}
c = max(coins)
nums = calc_ways(n, coins, cache, c)
return nums
def calc_ways(n, coins, cache, current_coin):
if n < 0:
return 0
if n == 0:
return 1
if n not in cache:
cache[n] = sum(calc_ways(n - c, coins, cache, c) for c in coins if c <= current_coin)
return cache[n]
answer = calc_change(n, coins)
print answer
Thank you for any help.
You are indexing cache according to the amount you want to add up to n. The problem is that the amount of combinations for the same n can change depending on the set of coins that you want to consider. (e.g. n=10 and coins=[10,5] has two possible combinations, but n=10 and coins=[5] has only one combination. You need your cache to consider the current_coin variable.
def calc_change(n, coins):
cache = {}
c = max(coins)
nums = calc_ways(n, coins, cache, c)
return nums
def calc_ways(n, coins, cache, current_coin):
if n < 0:
return 0
if n == 0:
return 1
if (n,current_coin) not in cache:
cache[(n,current_coin)] = sum(calc_ways(n - c, coins, cache, c) for c in coins if c <= current_coin)
return cache[(n,current_coin)]
answer = calc_change(n, coins)
print answer