Count Exact Sum
Given a list of positive integers nums and an integer k, return the number of subsets in the list that sum up to k.
Mod the result by 10 ** 9 + 7.
Constraints
n ≤ 300wherenis the length ofnums.k ≤ 300.
https://binarysearch.com/problems/Count-Exact-Sum
ExamplesPermalink
Example 1Permalink
Input
- nums =
[1, 2, 3, 4, 5] - k =
5
Output
- answer =
3
Explanation
We can choose the subsets [1,4],[2,3] and [5].
Example 2Permalink
Input
- nums =
[1, 2, 3, 4, 5] - k =
10
Output
- answer =
3
Explanation
We can choose the subsets [1,4,5],[2,3,5] and [1,2,3,4].
SolutionPermalink
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import functools | |
| class Solution: | |
| def solve(self, nums, k): | |
| # similar to 0-1 Knapsack, two choices at every | |
| # step are to either include or exclude the item | |
| mod = 10 ** 9 + 7 | |
| @functools.cache | |
| def solveR(idx, sub_sum): | |
| if idx == len(nums) or sub_sum >= k: | |
| return int(sub_sum == k) | |
| include = solveR(idx + 1, sub_sum + nums[idx]) | |
| exclude = solveR(idx + 1, sub_sum) | |
| return (include + exclude) % mod | |
| return solveR(0, 0) |
Leave a comment