Python程式：查詢和為k的不同組合的數量

假設我們有一個名為nums的不同數字列表和另一個數字k，我們需要找到和為k的不同組合的數量。在建立組合時，您可以重複使用數字。

因此，如果輸入類似於nums = [2, 4, 5] k = 4，則輸出將為2，因為我們可以建立兩個這樣的組，例如[2, 2]和[4]。

為了解決這個問題，我們將遵循以下步驟

  • table := 一個大小為k + 1的列表，並用0填充
  • table[0] := 1
  • 對於nums中的每個num，執行以下操作
    • 對於從num到k的範圍內的每個i，執行以下操作
      • table[i] := table[i] + table[i - num]
  • 返回table[k]

讓我們檢視以下實現以獲得更好的理解

示例程式碼

線上演示

class Solution:
   def solve(self, nums, k):
      table = [1] + [0] * k

      for num in nums:
         for i in range(num, k + 1):
            table[i] += table[i - num]

         return table[k]

ob = Solution()
nums = [2, 4, 5]
k = 4
print(ob.solve(nums, k))

輸入

[2, 4, 5], 4

輸出

2

更新於: 2020年11月25日

341 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告