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 2^40 enumeration is too slow and a DP over sums is impossible. Aim for 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.