Making the same amount from different combinations of coins (top-down approach)

I was reading a typical interview question found here. Given an amount and a list of denominations, count the number of possible ways to break the amount into different combinations of coins. For example, if amount = 4 and denominations=[1, 2, 3], there are 4 possibilities. Here's my Python solution.

def _get_num_of_changes(amount, denominations, i=0):
if amount == 0:
return 1
elif amount < 0:
return None
else:
s = 0
for i in range(i, len(denominations)):
coin = denominations[i]
if amount - coin < coin:
c = _get_num_of_changes(amount - coin, denominations, i+1)
else:
c = _get_num_of_changes(amount - coin, denominations, i)

if c:
s += c
return s

def get_num_of_changes(amount, denominations):
return _get_num_of_changes(amount, denominations)

print(get_num_of_changes(4, [1, 2, 3]))


This is a top-down solution in the sense that I subtract from the starting amount and not try to add coins starting at zero to get to amount (which would be a bottom-up solution). Given this difference, I am really interested to see if my solution is good enough, too.

Simpler base case

I suggest returning 0 as the base case to avoid the if c check di as x += 0 does not change it.

Iterate at a higher level

Use for item in collection not range(len. The index can be obtained with enumerate.

Avoid repetition

You repeat _get_num_of_changes(amount - coin, denominations, twice, use a ternary conditional expression to avoid it.

Avoid manual summing

Starting at $0$ and writing += is too manual in Python, I suggest using sum.

• I don't really understand what you mean in your third point. Wouldn't using a ternary expression in this case make a really long line (which one would generally like to avoid)? – bourbaki4481472 Feb 18 '16 at 18:57
• @bourbaki4481472 Just use a temporary variabile. – Caridorc Feb 18 '16 at 19:04

The function is computing rather than retrieving, so I wouldn't have "get" in the function name.

If the amount is negative, then there are zero ways to make the amount. There's no need to treat None as a special case.

Repurposing i in for i in range(i, len(denominations)) is confusing. The code would be clearer if you renamed the loop variable to j or something.

Still, having i as a parameter at all is awkward. I'd rather change the recursion strategy altogether. Instead of trying to use one of each denomination, why not exhaust one denomination altogether?

def num_change_combinations(amount, denominations):
if amount == 0:
return 1
elif amount < 0 or not denominations:
return 0
else:
coin = denominations[-1]
return sum(
num_change_combinations(amt, denominations[:-1])
for amt in range(amount, -1, -coin)
)

• Great comment on the use of the word "get." This actually will help me write functions in the future because I am always confused when to use get vs compute (or make). – bourbaki4481472 Feb 18 '16 at 20:04