在Python中查找总和为k的不同组合的数量

假设我们有一个称为nums的不同数字列表和另一个数字k，我们必须找到总和为k的不同组合的数量。您可以在创建组合时重复使用数字。

因此，如果输入形如nums = [2, 4, 5]，k = 4，则输出将为2，因为我们可以制作两个这样的组合，如[2, 2]和[4]。

要解决此问题，我们将遵循以下步骤：

• table：大小为k + 1的列表，并用0填充
• table[0] = 1
• 对于nums中的每个数字，做以下操作：
  • 对于i从num到k，执行以下操作：
    • table[i] = table[i] + table[i – num]
• 返回table[k]

让我们看下面的实现以更好地理解：

更多Python相关文章，请阅读：Python 教程

代码示例：

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