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 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告