Chương trình đếm tập con có tổng bằng k trong Python

Cho danh sách số nums và giá trị k, tìm số tập con có tổng bằng k. Kết quả modulo 10⁹+7.

Ví dụ: nums=[2,3,4,5,7], k=7 → output 3 (tập con [2,5], [3,4], [7]).

Thuật toán DP (0/1 Knapsack đếm cách):

• dp[j] = số cách tạo tổng j từ các số đã xét
• Khởi tạo dp[0] = 1 (1 cách tạo tổng 0: chọn rỗng)
• Duyệt mỗi num trong nums:
  • Duyệt j từ k xuống 0 (quan trọng: duyệt ngược để không dùng 1 số nhiều lần)
  • Nếu num <= j: dp[j] = (dp[j] + dp[j-num]) % MOD
• Trả về dp[k]

Triển khai

class Solution:
    def solve(self, nums, k):
        dp = [0] * (k + 1)
        dp[0] = 1
        MOD = 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] %= MOD
        return dp[k] % MOD

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

Giải thích: DP 1D (space optimized từ 2D). Duyệt j ngược đảm bảo mỗi số chỉ dùng tối đa 1 lần (0/1 knapsack). Nếu duyệt xuôi (0..k) → unbounded knapsack (dùng không giới hạn lần). Phức tạp O(n×k) thời gian, O(k) không gian.