硬幣組合

 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]

    
ms = coin_combins(9,[2,3,5]) 
print(ms)
print(len(ms))

# Output:

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

程式功能

1. 輸入：

   • x：目標總和。
   • coins：硬幣面值列表。

2. 輸出：

   • 返回所有能組成總和 x 的硬幣組合。

3. 邏輯：

   • 使用動態規劃的方式儲存每個總和 ( j ) 的組合。
   • 通過 btrack 陣列保存不同總和的所有可能組合。

---

程式執行過程

輸入：

x = 9
coins = [2, 3, 5]

---

初始狀態

1. 建立 btrack：
   • btrack[j] 表示總和為 ( j ) 的所有組合。
   • 初始狀態：

     btrack = [[[]], [], [], [], [], [], [], [], [], []]
     

   • btrack[0] 為 [[]]，表示總和為 0 時，唯一的組合是空集合。

---

處理硬幣 ( 2 )

1. 遍歷總和 ( j = 2 ) 到 ( 9 )：
   • 當 ( j = 2 )：將 btrack[2 - 2] = btrack[0] 的每個組合加上 ( 2 )。

     btrack[2] = [[2]]
     

   • 當 ( j = 4 )：將 btrack[4 - 2] = btrack[2] 的每個組合加上 ( 2 )。

     btrack[4] = [[2, 2]]
     

   • 當 ( j = 6 )：將 btrack[6 - 2] = btrack[4] 的每個組合加上 ( 2 )。

     btrack[6] = [[2, 2, 2]]
     

   • 當 ( j = 8 )：將 btrack[8 - 2] = btrack[6] 的每個組合加上 ( 2 )。

     btrack[8] = [[2, 2, 2, 2]]
     

2. 處理完硬幣 ( 2 ) 後：

   btrack = [[[]], [], [[2]], [], [[2, 2]], [], [[2, 2, 2]], [], [[2, 2, 2, 2]], []]
   

---

處理硬幣 ( 3 )

1. 遍歷總和 ( j = 3 ) 到 ( 9 )：
   • 當 ( j = 3 )：將 btrack[3 - 3] = btrack[0] 的每個組合加上 ( 3 )。

     btrack[3] = [[3]]
     

   • 當 ( j = 6 )：將 btrack[6 - 3] = btrack[3] 的每個組合加上 ( 3 )。

     btrack[6] = [[2, 2, 2], [3, 3]]
     

   • 當 ( j = 9 )：將 btrack[9 - 3] = btrack[6] 的每個組合加上 ( 3 )。

     btrack[9] = [[3, 3, 3]]
     

2. 處理完硬幣 ( 3 ) 後：

   btrack = [[[]], [], [[2]], [[3]], [[2, 2]], [], [[2, 2, 2], [3, 3]], [], [[2, 2, 2, 2]], [[3, 3, 3]]]
   

---

處理硬幣 ( 5 )

1. 遍歷總和 ( j = 5 ) 到 ( 9 )：
   • 當 ( j = 5 )：將 btrack[5 - 5] = btrack[0] 的每個組合加上 ( 5 )。

     btrack[5] = [[5]]
     

   • 當 ( j = 7 )：將 btrack[7 - 5] = btrack[2] 的每個組合加上 ( 5 )。

     btrack[7] = [[2, 5]]
     

   • 當 ( j = 9 )：將 btrack[9 - 5] = btrack[4] 的每個組合加上 ( 5 )。

     btrack[9] = [[3, 3, 3], [2, 2, 5]]
     

2. 處理完硬幣 ( 5 ) 後：

   btrack = [[[]], [], [[2]], [[3]], [[2, 2]], [[5]], [[2, 2, 2], [3, 3]], [[2, 5]], [[2, 2, 2, 2]], [[3, 3, 3], [2, 2, 5]]]
   

---

返回結果

• btrack[9] = [[3, 3, 3], [2, 2, 5]]
• 輸出組合方式：

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

• 輸出組合數量：

  2
  

---

程式輸出

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