Meet in the Middle

You are given an array nums of up to 40 integers and a target goal. Find a subsequence whose sum is as close to goal as possible, and return the minimum absolute difference. This is LeetCode 1755. Closest Subsequence Sum, and it is the classic motivation for meet in the middle.

Why brute force fails

A subsequence is any subset of the array elements (maintaining order does not matter for sums). An array of length n has $2^n$ subsequences. For each one, you could compute its sum and track the closest to goal. When n = 20, $2^{20}$ is about a million, which is fine. But when n = 40, $2^{40}$ is over a trillion. No amount of constant-factor optimization will save you.

The constraint n <= 40 is the signature of meet in the middle. It is too large for full enumeration but exactly twice the size where full enumeration is comfortable. That factor of two is the clue.

The idea

Split the array into two halves of roughly equal size, each with about n/2 elements. Enumerate all $2^{n/2}$ subset sums for each half independently. That is about a million operations per half when n = 40. Now you have two lists of sums, call them left and right. The total sum of any subsequence of the original array is some element from left plus some element from right (where 0 appears in both lists, representing the empty subset from that half).

The problem reduces to: given two lists and a target, find one element from each list whose sum is closest to the target. Sort one list, then for each element in the other list, binary search for the complement. This combine step takes $O(2^{n/2} \log 2^{n/2})$ time.

Walking through a small example

Consider nums = [5, -7, 3, 5] and goal = 6.

Split: left half = [5, -7], right half = [3, 5].

Enumerate left sums (all subsets of [5, -7]):

• {} = 0
• {5} = 5
• {-7} = -7
• {5, -7} = -2

So left = [-7, -2, 0, 5] (sorted).

Enumerate right sums (all subsets of [3, 5]):

• {} = 0
• {3} = 3
• {5} = 5
• {3, 5} = 8

So right = [0, 3, 5, 8].

Combine: For each value r in right, we want the value l in left that makes l + r closest to 6. That means we want l closest to 6 - r.

• r = 0: want l closest to 6. Best is l = 5, giving sum 5, diff = 1.
• r = 3: want l closest to 3. Best is l = 5, giving sum 8, diff = 2. Or l = 0, giving sum 3, diff = 3. So diff = 2.
• r = 5: want l closest to 1. Best is l = 0, giving sum 5, diff = 1. Or l = 5, giving sum 10, diff = 4. So diff = 1.
• r = 8: want l closest to -2. Best is l = -2, giving sum 6, diff = 0. Exact match!

The answer is 0, achieved by the subsequence {-7, 5, 3, 5} with sum -7 + 5 + 3 + 5 = 6.

The code

from bisect import bisect_left

def minAbsDifference(nums, goal):
    n = len(nums)
    left_half = nums[:n // 2]
    right_half = nums[n // 2:]

    def all_sums(arr):
        sums = [0]
        for x in arr:
            sums += [s + x for s in sums]
        return sums

    left = sorted(all_sums(left_half))
    right = all_sums(right_half)

    best = float('inf')
    for r in right:
        target = goal - r
        # Binary search for closest value in left
        idx = bisect_left(left, target)
        if idx < len(left):
            best = min(best, abs(left[idx] - target))
        if idx > 0:
            best = min(best, abs(left[idx - 1] - target))

    return best

The all_sums function generates all $2^k$ subset sums of an array of length k by iteratively including or excluding each element. Sorting left enables binary search during the combine step.

Complexity analysis

Each half has at most n/2 elements, so each produces at most $2^{n/2}$ sums. Generating them takes $O(2^{n/2})$ time. Sorting the left list takes $O(2^{n/2} \log 2^{n/2}) = O(2^{n/2} \cdot n/2)$. The combine step does $2^{n/2}$ binary searches, each costing $O(\log 2^{n/2}) = O(n/2)$, for a total of $O(2^{n/2} \cdot n/2)$.

Overall: $O(2^{n/2} \cdot n)$ time and $O(2^{n/2})$ space. For n = 40, $2^{20} \cdot 40$ is about 40 million, well within time limits. Compare this to $2^{40} \approx 10^{12}$ for the brute force. The exponential base is the same, but the exponent has been halved, which is an enormous practical improvement.

Application: 4Sum II

LeetCode 454. 4Sum II gives you four arrays A, B, C, D each of length n. Count the number of tuples (i, j, k, l) such that A[i] + B[j] + C[k] + D[l] = 0.

The brute force iterates over all $n^4$ tuples. Meet in the middle splits the four arrays into two pairs: compute all pairwise sums A[i] + B[j] and all pairwise sums C[k] + D[l]. For each sum from the first pair, you need the count of the negation in the second pair. A hash map makes this $O(1)$ per lookup.

from collections import Counter

def fourSumCount(nums1, nums2, nums3, nums4):
    ab_sums = Counter(a + b for a in nums1 for b in nums2)
    count = 0
    for c in nums3:
        for d in nums4:
            count += ab_sums[-(c + d)]
    return count

This runs in $O(n^2)$ time and $O(n^2)$ space, a massive improvement over $O(n^4)$. The meet-in-the-middle structure is the same: split the problem in half, enumerate all combinations within each half, then combine using a fast lookup. Here the "halves" are two pairs of arrays, the "enumeration" is computing pairwise sums, and the "combine" is a hash map lookup instead of binary search.

When to recognize meet in the middle

The telltale signs:

• The problem involves subsets or combinations of n items where n is around 30-40 (too large for $2^n$ but fine for $2^{n/2}$).
• The problem can be decomposed: split the input, solve each half independently, then merge the results.
• The merge step can be done efficiently using sorting + binary search, two pointers, or a hash map.

For problems with four independent dimensions (like 4Sum II), n can be up to 200 because $n^2$ per half is manageable and the combine step is also $O(n^2)$.

Another application: Split Array With Same Average

LeetCode 805. Split Array With Same Average asks whether an array can be partitioned into two non-empty parts with equal averages. After algebraic reduction, this becomes: find a non-empty proper subset whose sum equals a specific target (proportional to the subset size). The array can have up to 30 elements, making $2^{30}$ too slow but $2^{15}$ feasible. Meet in the middle splits the array in half, enumerates subset sums (grouped by subset size) for each half, and checks whether any combination from the two halves hits the target. The grouping by size adds a layer of bookkeeping but the core split-enumerate-combine structure is identical.

Summary

Meet in the middle is a general technique for cutting an exponential search space in half. Split the input into two parts, enumerate all possibilities for each part independently, then combine the two halves using an efficient lookup structure. The time complexity drops from $O(2^n)$ to $O(2^{n/2} \cdot n)$, which transforms problems that would take centuries into ones that run in seconds. Look for it whenever n is in the 30-40 range and the problem involves subsets or combinations.

Recognizing this pattern

You're probably looking at meet in the middle when:

• The input size is awkward, typically $n$ in the range 30 to 45, so $2^n$ is too much but $2^{n/2}$ is comfortable.
• The problem asks about all subsets, all subsequences, or all combinations, with no obvious DP state.
• The objective can be decomposed additively (or multiplicatively, with logs) across the two halves so a left choice plus a right choice gives a full solution.
• Polynomial-time DP is blocked by huge value ranges (e.g., sums up to $10^9$), so you cannot do subset-sum DP.

Common templates:

• Closest subset sum: enumerate both halves, sort one, binary search for each value from the other. Example: Closest Subsequence Sum.
• Count subsets with target sum: enumerate halves, then count pairs $(L, R)$ with $L + R = \text{target}$ via a hash map. Example: Partition Array Into Two Arrays to Minimize Sum Difference.
• Subsets within a capacity: enumerate half-sums, sort, then for each left sum binary search the largest compatible right sum. Example: Sum of Subsequence Widths (and the general 0/1 knapsack for $n \le 40$).
• Bidirectional BFS as meet in the middle on graphs: search from start and goal simultaneously, halving the BFS depth. Example: Word Ladder.