Write two functions:
subset_sums(nums: list[int]) -> list[int]: the sums of all2^nsubsets (by position, so repeats are kept), sorted. The empty subset gives0.has_subset_sum(nums: list[int], target: int) -> bool: does some subset (possibly empty) sum to exactlytarget?
subset_sums([1, 2, 4]) # [0, 1, 2, 3, 4, 5, 6, 7]
subset_sums([3, 3]) # [0, 3, 3, 6]
subset_sums([]) # [0]
has_subset_sum([5, -2, 9, 4], 7) # True (5 + -2 + 4)
has_subset_sum([5, -2, 9, 4], 1) # False
nums has up to 36 values of size up to 10^9 (up to 18 for subset_sums), so a DP over sums is out.
⭐ Bonus: listing all 2^n subsets passes for small inputs; a speed test with 36 values earns a star with meet in the middle: split nums in two, list each half's 2^18 sums, put the right half's in a set, and check target - s for each left sum s.
Show hint
sums = [0]; for x in nums: sums += [s + x for s in sums].