硬幣組合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 = 10

coins = [2,3,5]

ms = coin_combins(x,coins) 

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

print(ms)

print(len(ms),'種')

# x = 10

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

# ms = coin_combins(x,coins) 

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

# print(ms)

# print(len(ms),'種')

# x = 16

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

# ms = coin_combins(x,coins) 

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

# print(ms)

# print(len(ms),'種')

# Output:

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

# [[2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 3, 5], [5, 5]]

# 4 種

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

# [[2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 3, 5], [5, 5], [10]]

# 5 種

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

# [[2, 2, 2, 2, 2, 2, 2, 2], [2, 2, 2, 2, 2, 3, 3], [2, 2, 3, 3, 3, 3], [2, 2, 2, 2, 3, 5], [2, 3, 3, 3, 5], [2, 2, 2, 5, 5], [3, 3, 5, 5], [2, 2, 2, 10], [3, 3, 10]]

# 9 種