progress

~/problems / Search tricks / Meet in the middle

Count subsets with a target sum

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

hard ~35 min

Write count_subsets(nums: list[int], x: int) -> int: the number of subsets of nums (chosen by position, so equal values at different positions are different choices) whose elements sum to exactly x. The empty subset has sum 0.

nums has up to 40 elements with values up to 10^9, so a DP over sums is impossible. ⭐ Bonus: listing all 2^n subsets passes small cases; speed tests with 34 values earn a star at about O(2^(n/2) · n).

count_subsets([3, 5, 2, 3], 8)   # 3: {3, 5} (first 3), {5, 3} (second 3), {3, 2, 3}
count_subsets([7], 7)            # 1
count_subsets([7], 0)            # 1 (the empty subset)
count_subsets([1, 2], 10)        # 0

Constraints: 1 ≤ len(nums) ≤ 40, 1 ≤ nums[i] ≤ 10^9, 0 ≤ x ≤ 10^9.

Show hint

Any subset is a subset of the first half of the list plus a subset of the second half, and each half has only about 2^20 subsets. Tally one half's subset sums in a dictionary, then look up what each of the other half's sums needs.

Topic: Meet in the middle. Split n ~ 40 into two halves of 2^20 and combine with sort + two pointers.

0:00
Ctrl ' run · Ctrl ↵ submit
esc