Make change using a given amount of coins. No memoization, for simplicity's sake.

changemaker.py

# The denominations
denoms = [1, 5, 10, 25]

def make_change(change, denoms):
    return _make_change(change, sorted(denoms, reverse=True))

def _make_change(cents, denoms):
    ways = []
    for denom in denoms:
        if cents == denom:
            ways.append([denom])
        if cents > denom:
            remainder = cents - denom
            for way in _make_change(remainder, denoms):
                if way[0] <= denom:
                    ways.append([denom] + way)
    return ways

for way in make_change(25, denoms):
    print way

changemaker_better.py

# The amounts. keys are the denomination, values are the amount of them.
amounts = {25: 1, 5: 5, 10: 2}

def make_change(change, amounts):
    return _make_change(change, sorted(amounts.keys(), reverse=True), amounts)

def _make_change(cents, denom_keys_sorted, amounts):
    ways = []
    for denom in denom_keys_sorted:
        amount = amounts[denom]
        if amount > 0:
            if cents == denom:
                ways.append([denom])
            if cents > denom:
                remainder = cents - denom
                m_amounts = amounts.copy()
                m_amounts[denom] -= 1
                for way in _make_change(remainder, denom_keys_sorted, m_amounts):
                    if way[0] <= denom:
                        ways.append([denom] + way)
    return ways

for way in make_change(50, amounts):
    print way

changemaker_better_memo.py

from collections import OrderedDict as odict
INFINITY = 999

# The amounts. keys are the denomination, values are the amount of them.
amounts = odict({25: INFINITY, 5: INFINITY, 10: INFINITY, 1:INFINITY})
change = 120

_memo = {}

def make_change(cents, amounts):
    amounts_state = tuple(amounts.values())
    if amounts_state in _memo:
        return _memo[amounts_state]
    
    ways = []
    for denom, amount in amounts.items():
        if amount > 0:
            if cents == denom:
                ways.append([denom])
            if cents > denom:
                remainder = cents - denom
                m_amounts = amounts.copy()
                m_amounts[denom] -= 1
                for way in make_change(remainder, m_amounts):
                    if way[0] <= denom:
                        ways.append([denom] + way)

    _memo[amounts_state] = ways
    
    return ways

results = make_change(change, amounts)

for way in results:
    print way
if not results:
    print "No results!"
print "Done"
print "Ways: ", len(results)

too slow D: