BinarySearch 0422 Count Exact Sum

Problem statement

https://binarysearch.com/problems/Count-Exact-Sum/

Solution

Use dp technique here, where dp is how many subset with given sum we have when we used first i nubmers.

Complexity

It is O(k * n) for time and O(k) for space.

Code

class Solution:
    def solve(self, nums, k):
        dp = [1] + [0] * k
        for num in nums:
            dp2 = dp
            for x in range(k - num, -1, -1):
                dp2[x + num] += dp[x]
            dp = [x % (10**9 + 7) for x in dp2]
        
        return dp[-1]