最大硬幣值優先 II

 def coin_combins(x,coins):

  btrack = [[] for i in range(x+1)]

  btrack[0].append([])

  

  for coin in coins:

    for j in range(coin,x+1):

      for combin in btrack[j-coin]:

        btrack[j].append(combin+[coin])

        

  return btrack[x]

x = 200

coins = [2,3,5,10,50]

ms = coin_combins(x,coins) 

print('金額:',x,'硬幣：',coins)

ms.reverse()

print(len(ms),'種解法')

print('5種解法：',ms[:5])

# Output:

# 金額: 200 硬幣： [2, 3, 5, 10, 50]

# 8299 種解法

# 5種解法： [[50, 50, 50, 50], [10, 10, 10, 10, 10, 50, 50, 50], [5, 5, 10, 10, 10, 10, 50, 50, 50], [2, 3, 5, 10, 10, 10, 10, 50, 50, 50], [2, 2, 3, 3, 10, 10, 10, 10, 50, 50, 50]]