progress

~/problems / Search tricks / Meet in the middle

Subset sums of two halves

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

easy basics ~10 min

Write two functions:

  1. subset_sums(nums: list[int]) -> list[int]: the sums of all 2^n subsets (by position, so repeats are kept), sorted. The empty subset gives 0.
  2. has_subset_sum(nums: list[int], target: int) -> bool: does some subset (possibly empty) sum to exactly target?
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].

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