擅长:python、mysql、java
<p>这是问题的一个完整的解决方案,整个函数是一个伪装的大生成器,第一个<code>for</code>循环使用最小的硬币,在第二个循环中,最小的硬币被丢弃,下一个大的硬币将成为我们递归函数的基础。如果列表中的硬币数量大于当前列表中的总和,则将其返回给当前列表。在</p>
<pre><code>def changes(number, coins_available, coins_current):
if sum(coins_current) == number:
yield coins_current
elif sum(coins_current) > number:
pass
elif coins_available == []:
pass
else:
for c in changes(number, coins_available[:], coins_current + [coins_available[0]]):
yield c
for c in changes(number, coins_available[1:], coins_current):
yield c
n = 40
coins = [1,2,5,10,20,50,100]
solutions = [sol for sol in changes(n, coins, [])]
for sol in solutions:
print sol
print 'least coins used solution:', min(solutions, key=len)
print 'number of solutions', len(solutions)
</code></pre>