5
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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)? \$\endgroup\$ – bourbaki4481472 Feb 18 '16 at 18:57
  • \$\begingroup\$ @bourbaki4481472 Just use a temporary variabile. \$\endgroup\$ – Caridorc Feb 18 '16 at 19:04
2
\$\begingroup\$

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) 
        )
\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – bourbaki4481472 Feb 18 '16 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.