Count subsets with sum

Count the number of subsets of a list that sum to a target value.

subset-sum dynamic-programming counting

Write a function `count_subsets(nums, target)` that returns the number of subsets of `nums` whose elements sum up to `target`.

A subset is any selection of elements from the list, where each element can be chosen at most once. The order of elements does not matter, and two subsets are considered different if they select different positions in the original list (even if values are equal). The empty subset is allowed and sums to 0.

Your implementation should handle lists with up to 30 elements efficiently using dynamic programming. You may assume that `nums` contains integers (possibly negative) and `target` is an integer.

Examples:
- `count_subsets([1, 2, 3], 3)` returns `2` (subsets [1,2] and [3]).
- `count_subsets([1, 1, 1], 2)` returns `3` (any two of the three ones).
- `count_subsets([1, 2, 3], 100)` returns `0`.
- `count_subsets([-1, 1, 0], 0)` returns `4` (subsets [], [-1, 1], [0], and [-1, 0, 1]).

Return an integer count. The answer will fit in a 64-bit integer.

Constraints

- `0 <= len(nums) <= 30`
- `-1000 <= nums[i] <= 1000`
- `-10000 <= target <= 10000`
- The number of subsets can be large; ensure your solution uses memoization or DP to avoid exponential time.

Example

>>> count_subsets([1, 2, 3], 3)
2
>>> count_subsets([1, 1, 1], 2)
3
>>> count_subsets([1, 2, 3], 100)
0
>>> count_subsets([-1, 1, 0], 0)
4

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of the problem as a subset-sum counting problem. Each element can be either included or excluded.

Consider using memoization with a dictionary that maps (index, current_sum) to the number of ways.

For large inputs, a DP table over possible sums can be used; start with a dictionary mapping sum 0 to 1 and update for each number.

Handle negative numbers by using a dictionary to store possible sums and their counts, not a fixed-length array.

Test Results

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