Articles

Meet-in-the-Middle Interview Questions: Subset Sums, Negative Values, and Memory Limits

Practice meet-in-the-middle subset sums with negative values: trace the split, find the closest pair, reconstruct a witness, and plan memory use.

“Forty integers may be positive or negative. Find a subset whose sum is closest to a target. Would you build a table indexed by the target?” A good interview answer starts with the constraint that breaks that idea: the target can be large, and negative values invalidate positive-only pruning. Meet-in-the-middle (MITM) splits the input into two groups, enumerates each group’s sums, and joins the two lists to find the closest pair. The exponential exponent falls from n to about n/2, but the stored half-lists become the new limit.

This guide builds one signed example, reconstructs the chosen subset, and makes the memory cost explicit. Evidence boundary: LeetCode’s official Closest Subsequence Sum statement supplies a concrete 40-element, signed-value task. The example, implementation choices, and interview rubric below are original editorial work, not a candidate report about a particular employer.

When does splitting beat direct enumeration?

A subset of n occurrences has 2^n inclusion masks. With n = 40, direct enumeration would consider about 1.10 trillion masks, before worrying about output or sorting. Splitting into halves of 20 yields 2^20 = 1,048,576 masks on each side. You still do substantial work, but roughly two million generated sums plus a join are much more plausible than a trillion full subsets.

The split is by input occurrence, not by value or sign. Each half receives a slice of the original indices. Choosing the left mask and right mask uniquely specifies a full subset, even when values repeat. That observation is the correctness bridge: every full subset can be decomposed into one subset of the left half and one of the right half, and every such pair is a legal full subset. Splitting does not discard a candidate; it changes how candidates are organized.

First clarify the output. LeetCode 1755 asks only for the minimum absolute difference from the goal. An interviewer may ask for the sum, the indices, all optimal subsets, or the count of solutions. Those are different contracts. A method that keeps only unique sums may preserve the minimum difference but lose distinct witnesses or multiplicities. State whether the empty subset is allowed, whether repeated input values represent distinct occurrences, and how ties are broken before optimizing storage.

Work a signed example all the way through

Use the original exercise nums = [7, -4, 6, -9, 3, 8], goal = 5. Split after the third occurrence: left [7, -4, 6], right [-9, 3, 8]. Enumerate sums with masks, including the empty subset.

Left mask	Selected values	Sum
`000`	none	0
`001`	7	7
`010`	-4	-4
`011`	7, -4	3
`100`	6	6
`101`	7, 6	13
`110`	-4, 6	2
`111`	7, -4, 6	9

The right sums, before sorting, are 0, -9, 3, -6, 8, -1, 11, 2. For a left sum of 3, the ideal right sum is goal - 3 = 2; the right mask choosing -9, 3, 8 yields exactly 2, so the full subset [7, -4, -9, 3, 8] sums to 5. That explicit pair establishes minimum difference 0, which cannot be beaten.

That last sentence models an important interview habit: distinguish a sum from its witness. If all you store is the numeric sum, you can answer the difference but cannot always identify which occurrences produced it. Store (sum, mask) if reconstruction matters. Duplicates are not an error: they may represent different index choices with the same sum. You can compress sums only after you establish that the requested output permits it.

Join with binary search or two pointers

Sort the right half by sum. For each left sum L, search for goal - L; the closest right candidate is at the insertion point or immediately before it. Check both neighbors because the target complement may fall between two right sums. Record the best absolute difference and its two masks. With A = 2^ceil(n/2) and B = 2^floor(n/2), generation takes O(n(A+B)) in a simple implementation that sums each mask from scratch, right sorting takes O(B log B), and joining takes O(A log B). Incremental mask generation can reduce arithmetic work, but it does not eliminate the A+B list size.

A second approach sorts both lists, places one pointer at the smallest left sum and one at the largest right sum, and compares L+R with the goal. If the sum is too small, advance the left pointer; if too large, decrease the right pointer. The pointer movement is safe because each list is sorted: no skipped pair on the discarded side can improve the direction needed to cross the target at that step. It finds the closest sum in O(A+B) after sorting, and can retain the masks. Binary search may be simpler when you already have one sorted list; two pointers are attractive when you want a single monotone sweep.

Neither method says “sort the original numbers and greedily choose.” The sorted objects are complete half-subset sums. A negative value can cause a later inclusion to reduce an overshoot, so a prefix of positive-only pruning rules is not valid. For example, with values [10, -9] and target 1, abandoning a partial sum of 10 as too large would miss the exact solution. You may still derive safe bounds from remaining positive and negative totals, but explain those bounds rather than borrowing a rule from a nonnegative problem.

A witness-preserving Python sketch

The following code returns both the minimum difference and original indices. Its list sizes are intentional; that makes the memory trade-off visible instead of hiding it inside a set or recursive cache.

from bisect import bisect_left

def half_sums(values):
    out = []
    for mask in range(1 << len(values)):
        total = sum(value for i, value in enumerate(values)
                    if mask & (1 << i))
        out.append((total, mask))
    return out

def closest_subset(nums, goal):
    cut = len(nums) // 2
    left = half_sums(nums[:cut])
    right = sorted(half_sums(nums[cut:]))
    right_totals = [total for total, _ in right]
    best = None

    for left_total, left_mask in left:
        pos = bisect_left(right_totals, goal - left_total)
        for j in (pos - 1, pos):
            if 0 <= j < len(right):
                right_total, right_mask = right[j]
                candidate = (abs(goal - left_total - right_total),
                             left_mask, right_mask)
                if best is None or candidate < best:
                    best = candidate

    difference, left_mask, right_mask = best
    indices = [i for i in range(cut) if left_mask & (1 << i)]
    indices += [cut + i for i in range(len(nums) - cut)
                if right_mask & (1 << i)]
    return difference, indices

The lexicographic tuple comparison gives a deterministic tie-break over masks, not a promise of the smallest subset, smallest values, or lexicographically smallest index list. If the interviewer specifies one of those policies, compare that property explicitly. This code is a clarity baseline: sum(...) for every mask adds a factor of half-length to generation. A production-sized implementation can compute successive mask sums or Gray-code transitions, but it should keep the same witness mapping and correctness tests.

Test [] if the API allows an empty input, a zero target, all-negative values, duplicate occurrences, and a target beyond every possible sum. Check a case where the best right complement is just below the insertion point and one where it is just above. Compare against exhaustive full enumeration for small n; do not validate the join against another implementation with the same search error.

Memory is the other half of the answer

At n=40, each side can have 1,048,576 entries. In a low-level language, an eight-byte sum and a four-byte mask already consume about 12 MiB per million entries before padding, sort buffers, and allocator overhead. In Python, tuples and arbitrary-precision integers cost substantially more; two million Python tuples plus a second list of right sums can be hundreds of MiB in a real interpreter. Treat that as an order-of-magnitude warning, not a measured benchmark for every runtime. Measure with the target language and memory limit.

You can often store only one full half-list: enumerate the other half one sum at a time, binary-search the sorted stored side, and keep the current best. For a difference-only answer, deduplicating equal stored sums may save space, but sorting still needs the original list unless you use an external sort or another representation. If a tight memory cap makes 2^(n/2) entries impossible, MITM may not be the correct solution. Depending on value range and target, bitset or offset dynamic programming, branch-and-bound with sound signed bounds, or a more specialized algorithm may be better. There is no universal “MITM is always fastest” rule.

A bitset indexed by target works well when values and reachable range are modest and the transition rules match the task. In LeetCode 1755, signed values can have magnitude up to 10^7 and the goal up to 10^9, so a naïve target-indexed table is a poor default. Do not claim dynamic programming is mathematically impossible; say its state-space dimension is unattractive under these constraints. Conversely, if there are 28 numbers but the total absolute sum is only a few thousand, a range-indexed DP may be smaller than two 16-thousand-entry lists.

Interview follow-ups that expose the invariant

Why is the split complete? Every original index belongs to exactly one half. Any full mask is the concatenation of one left and one right mask, so every legal subset is represented by one pair.

Why search only two right neighbors? Once right sums are sorted, the closest numeric value to the desired complement lies at the lower bound or immediately before it. Farther entries on either side cannot be closer. If ties need multiple witnesses, inspect the equal-sum run or specify a tie policy.

Can I stop when I find difference zero? Yes for a minimum-difference-only objective: zero is a global lower bound. Not necessarily if the output requires every exact subset, a count, or a particular tie-break.

What about overflow? Bound the largest possible absolute subset sum using sum(abs(x) for x in nums), add the goal-magnitude bound, and choose an integer type that can represent intermediate sums and differences. Python integers grow; fixed-width languages need an explicit choice.

Does negative input change binary search? No. Signed sums sort in the usual numeric order. Negatives break some pruning assumptions and range-indexed DP sizing, not the nearest-neighbor property of a sorted list.

What if the question asks for all exact subsets? Output itself may be exponential. Grouping identical sums can help lookup, but each witness must remain recoverable; report output-sensitive complexity rather than quoting only the closest-sum complexity.