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.