Chương trình đếm các tập hợp con có tổng đến k trong python

Giả sử chúng ta có một danh sách các số gọi là num và một giá trị khác k, chúng ta phải tìm số lượng các tập con trong danh sách có tổng bằng k. Nếu câu trả lời là rất lớn, hãy sửa đổi điều này với 10 ^ 9 + 7

Vì vậy, nếu đầu vào là nums =[2, 3, 4, 5, 7] k =7, thì đầu ra sẽ là 3, vì Chúng ta có thể chọn các tập con [2,5], [3,4] và [ 7].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• dp:=danh sách kích thước (k + 1) và điền bằng 0
• dp [0]:=1
• m:=10 ^ 9 + 7
• đối với tôi trong phạm vi từ 0 đến kích thước là nums - 1, thực hiện
  • cho j trong phạm vi k giảm xuống 0, giảm 1, thực hiện
    • nếu nums [i] <=j, thì
      • dp [j]:=dp [j] + dp [j - nums [i]]
      • dp [j]:=dp [j] mod m

• return dp [k] mod m

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

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

Đầu ra

3