HiveBrain v1.2.0
Get Started
← Back to all entries
principlepythonMinor

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

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
fromsamethetopcombinationsamountcoinsdifferentdownmaking

Problem

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.

Solution

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.

Context

StackExchange Code Review Q#120423, answer score: 2

Revisions (0)

No revisions yet.