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
for i in range 0 to size of nums – 1，do
- for j in range k down to 0，减少1，do
  - if nums [i] <= j，则
  - dp [j]：= dp [j] + dp [j-nums [i]]
  - dp [j]：= dp [j] mod m
返回dp [k] mod m

以下是实现的示例，以便更好地理解−

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

例

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））