Hey
I'd like some some critique on an algorithm I was tasked to write. It does yield the right answer, but due to inexperience I have no clue whether the implementation is any good beyond that.
Here's the exercise:
Quote
Write a function f which given the change amount and a list of all existing coins in a curreny, returns all possible ways to give out the change money. Example: with change == 6 and coins == [1, 5, 10, 25, 27], f(change, coins) should return [[5, 1], [1, 1, 1, 1, 1, 1]].
Here's my code:
Code
def changeCombs(change, currencyCoins, memo = None, firstCall = True):
if not memo:
memo = {0:[[]]}
if change in memo:
return memo[change]
allcombs = []
for coin in currencyCoins:
if change - coin >= 0:
for subcomb in changeCombs(change - coin, currencyCoins, memo, False):
comb = [coin] + subcomb
comb.sort()
comb.reverse()
if comb not in allcombs:
allcombs.append(comb)
memo[change] = allcombs
if firstCall:
return sorted(allcombs, key = lambda lst: len(lst))
return allcombs
Thanks!