coins = [8, 5, 1]

def fixed_size(coins, n):
    if n == 0:
        return {'': 0}
    if coins == []:
        return {}
    if n == 1:
        r = {}
        for x in coins:
            r[str(x)] = x
        return r
    with_fewer = fixed_size(coins, n - 1)
    with_it = {}
    for x in with_fewer:
        with_it[x + ' + ' + str(coins[0])] = with_fewer[x] + coins[0]
    without_it = fixed_size(coins[1:], n)
    r = {}
    for x in with_it:
        r[x] = with_it[x]
    for x in without_it:
        r[x] = without_it[x]
    return r

def up_to_size(coins, n):
    r = {}
    for k in range(n + 1):
        f = fixed_size(coins, k)
        for x in f:
            r[x] = f[x]
    return r

def print_sorted_dict(d):
    dd = dict(sorted(d.items()))
    for k in dd:
        print(k, ':', dd[k])