logic is a good idea, "evenly divisible" isn't particularly useful. Let's try this:
Code:

def change(total, denominations, current, result):
'''
doctest. Run doctest with command
$ python -m doctest thisfile.py
>>> result = []
>>> change(total = 10, denominations = [5, 10], current = [], result = result)
>>> assert len(result) == 2
>>> assert [5, 5] in result
>>> assert [10] in result
'''
# recursion rule: find a way to stop the recursion
s = sum(current)
if s == total: # if the sum is correct, append the result
result.append(current)
if total <= s: # if the sum is correct or too large, return.
return
# recursively try all the possibilities
for denomination in denominations:
change(total, denominations, current+[denomination], result)

Simple, and it passes the test, but I think it's wrong. Example:

Code:

>>> result = []
>>> change(10, [1, 5, 10], [], result)
>>> print(result)
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 5, 1], [1, 1, 1, 5, 1, 1], [1, 1, 5, 1, 1, 1], [1, 5, 1, 1, 1, 1], [5, 1, 1, 1, 1, 1], [5, 5], [10]]

Change does not depend on order. The algorotithm could additionally post process the output by sorting each of the lists then retain only the unique entries.

Or we could not create the entries in the first place. This version of the algorithm works from biggest to smallest thereby avoiding the problem.
Code:

def change(total, denominations, current, result):
'''
doctest. Run doctest with command
$ python -m doctest thisfile.py
>>> result = []
>>> change(total = 10, denominations = [5, 10], current = [], result = result)
>>> assert len(result) == 2
>>> assert [5, 5] in result
>>> assert [10] in result
'''
# recursion rule: find a way to stop the recursion
s = sum(current)
if s == total: # if the sum is correct, append the result
result.append(current)
if total <= s: # if the sum is correct or too large, return.
return
denominations.sort(reverse = True) # use a sorting step
# recursively try all the possibilities
for (i, denomination,) in enumerate(denominations):
change(total, denominations[i:], current+[denomination], result)

Tweet This+ 1 thisPost To Linkedin