Pythonで「お題：ある金額になるコインの組み合わせ」をやってみた

お題：ある金額になるコインの組み合わせをPythonでやってみた。
バックトラックが一番簡単か。
「順序が違うだけのものは一つの組み合わせとする」は「各列をソートしたときに重複しない」と同じ。探索する候補が列の最後の値を下回らない([x for x in coins if path[-1] <= x])ようにするとソートされた列が得られる。

#!/usr/bin/env python
# coding: utf-8

def hoge(coins, amount):
    """
    >>> result = list(hoge([1, 5, 10, 50, 100, 500], 10))
    >>> len(result)
    4
    >>> result
    [[10], [5, 5], [1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
    """
    stack = [(coins, amount, [0])]
    while stack:
        coins, amount, path = stack.pop()
	if amount == 0:
	    yield path[1:]
	elif amount > 0:
            candidate = [x for x in coins if path[-1] <= x]
	    for coin in candidate:
		stack.append((candidate, amount - coin, path + [coin]))

if __name__ == "__main__":
    result = list(hoge(map(int, raw_input("コインの種類:").split(',')), int(raw_input("金額:"))))
    print "組み合わせ数:", len(result)
    print "組み合わせ:"
    for i in reversed(result):
        print i