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

Question

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.

Answer 1

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.

• under_the_sea_salad: 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)?
• Caridorc: @bourbaki4481472 Just use a temporary variabile.

Answer 2

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

• under_the_sea_salad: 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).