Target Sum Subsets

Count distinct subsets that sum to a given target using dynamic programming.

subset-sum dp counting combinatorics

Given a list of positive integers `nums` and a target integer `target`, return the number of distinct subsets of `nums` whose sum equals `target`. A subset can be any selection of elements from `nums`, and each element can be used at most once.

Implement the function `count_subset_sum(nums: List[int], target: int) -> int` that returns the count as an integer.

Note: The order of elements in the subset does not matter. Two subsets are considered different if they select different positions from `nums`, even if the values are the same.

For example, with `nums = [1, 2, 3]` and `target = 3`, the subsets that sum to 3 are `[3]` and `[1, 2]`, so the answer is 2.

Constraints

- 0 <= len(nums) <= 30
- 1 <= nums[i] <= 100
- 0 <= target <= 1000
- The sum of all numbers in `nums` may be large, but the answer will fit within a 64-bit integer.
- Your solution should have time complexity O(len(nums) * target) and space complexity O(target) or better.

Example

>>> count_subset_sum([1, 2, 3], 3)
2
>>> count_subset_sum([1, 1, 1], 2)
3
>>> count_subset_sum([2, 4, 6], 5)
0
>>> count_subset_sum([], 0)
1

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about the classic subset sum DP where dp[t] holds the number of ways to form sum t.

Iterate through each number and update dp from the highest target down to the number itself to avoid reusing the same number.

The base case is dp[0] = 1: there is exactly one way to form sum 0 — take no elements.

Be careful with an empty nums list and target 0 — the answer should be 1.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.