程序在python中计算总计为k的子集

假设我们有一个称为nums的数字列表，另一个值为k，我们必须在列表中找到总计为k的子集数量。如果答案很大，则用10 ^ 9 + 7修改

因此，如果输入像nums = [2，3，4，5，7] k = 7，则输出将为3，因为我们可以选择子集[2,5]，[3,4]和[ 7]。

为了解决这个问题，我们将遵循以下步骤-

• dp：=大小（k + 1）的列表，并用0填充

• dp [0]：= 1

• m：= 10 ^ 9 + 7

• 对于范围从0到nums的i-1，执行

• 如果nums [i] <= j，则

• dp [j]：= dp [j] + dp [j-数字[i]]

• dp [j]：= dp [j] mod m

• 对于范围k中的j减小到0，减小1，

• 返回dp [k] mod m

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

例 

class Solution:
   def solve(self, nums, k):
      dp = [0] * (k + 1)
      dp[0] = 1
      m = int(1e9 + 7)
      for i in range(len(nums)):
         for j in range(k, -1, -1):
            if nums[i] <= j:
               dp[j] += dp[j - nums[i]]
               dp[j] %= m
      return dp[k] % m

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

输入值

[2, 3, 4, 5, 7], 7

输出结果

3