principlepythonMinor
Making the same amount from different combinations of coins (top-down approach)
Viewed 0 times
fromsamethetopcombinationsamountcoinsdifferentdownmaking
Problem
I was reading a typical interview question found here. Given an
This is a top-down solution in the sense that I subtract from the starting
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.Solution
Simpler base case
I suggest returning
Iterate at a higher level
Use
Avoid repetition
You repeat
Avoid manual summing
Starting at \$0\$ and writing
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.Context
StackExchange Code Review Q#120423, answer score: 2
Revisions (0)
No revisions yet.