Closest Subsequence Sum: Meet in the Middle

LeetCode Closest Subsequence Sum (problem 1755) gives you an integer array nums and an integer goal. You need to find a subsequence of nums whose sum is as close to goal as possible. Return the minimum absolute difference between the sum of any subsequence and goal. A subsequence can include any subset of the elements (including the empty set).

Why this problem matters

This problem is a textbook example of the "meet in the middle" technique. The constraint that nums can have up to 40 elements is the dead giveaway. Brute-forcing all 2^40 subsets (about 1 trillion) is far too slow. But if you split the array in half, each half has at most 2^20 subsets (about 1 million), which is perfectly feasible. This halving trick turns an intractable exponential problem into a manageable one.

Meet in the middle shows up in competitive programming and interview prep alike. Once you recognize the pattern, you can apply it to any problem where the full search space is too large but half the search space fits comfortably. It is also a great example of how sorting plus binary search can combine with enumeration to produce efficient hybrid algorithms.

The key insight

The array can have up to 40 elements. Enumerating all 2^40 subsets is not going to work. But notice what happens if you split the array into two halves of size 20. Each half has at most 2^20 subsets, which is roughly 1 million. You can enumerate all subset sums for each half in about 1 million operations each. That is fast.

Once you have two lists of subset sums (one for the left half, one for the right half), the problem reduces to: find one value from each list such that their sum is as close to goal as possible. This is a classic two-list search problem. Sort one list, then for each value in the other list, binary search for the complement that gets you closest to the target.

Here is the algorithm:

1. Split nums into two halves: left and right.
2. Generate all possible subset sums for left (call them left_sums) and for right (call them right_sums).
3. Sort right_sums.
4. For each sum s in left_sums, binary search in right_sums for the value closest to goal - s.
5. Track the minimum absolute difference across all pairs.

The solution

from bisect import bisect_left

def min_abs_difference(nums, goal):
    n = len(nums)
    left, right = nums[:n // 2], nums[n // 2:]

    def get_sums(arr):
        sums = {0}
        for x in arr:
            sums = sums | {s + x for s in sums}
        return sorted(sums)

    left_sums = get_sums(left)
    right_sums = get_sums(right)

    best = float("inf")
    for s in left_sums:
        target = goal - s
        idx = bisect_left(right_sums, target)
        if idx < len(right_sums):
            best = min(best, abs(s + right_sums[idx] - goal))
        if idx > 0:
            best = min(best, abs(s + right_sums[idx - 1] - goal))

    return best

The get_sums function generates all subset sums for a given array. It starts with a set containing just {0} (the empty subset) and iteratively adds each element to all existing sums. After processing every element, the set contains all possible subset sums.

The main function splits the array, generates both lists of sums, sorts the right list, then loops through each left sum. For each left sum, it binary searches in the sorted right list for the value closest to goal - s. Because bisect_left returns the insertion point, you need to check both the element at that index (the first value that is at least target) and the element just before it (the largest value less than target). The minimum across all these checks is the answer.

Visual walkthrough

Let's trace through the algorithm with nums = [5, -7, 3, 5] and goal = 6. The array is small enough to see every step clearly.

The pair left = -2 and right = 8 gives a total of 6, which matches the goal exactly. This corresponds to the subsequence that includes all four elements: 5 + (-7) + 3 + 5 = 6. Not every input will produce an exact match, but the binary search guarantees we find the closest possible pair.

Complexity analysis

Time: We generate 2^(n/2) subset sums for each half, which takes O(2^(n/2)) time per half. Sorting the right sums takes O(2^(n/2) * log(2^(n/2))). The binary search loop iterates over each of the 2^(n/2) left sums and does a O(log(2^(n/2))) binary search for each. Since log(2^(n/2)) simplifies to n/2, the overall time simplifies to O(n * 2^(n/2)). For n = 40, that is about 20 million operations, well within time limits.

Space: We store 2^(n/2) subset sums for each half. For n = 40, that is about 1 million integers per half, which fits comfortably in memory.

The building blocks

1. Generating all subset sums

This is the enumeration step at the core of meet in the middle. For a small array, you iterate through each element and, for every sum computed so far, create a new sum by adding the current element:

def get_sums(arr):
    sums = {0}
    for x in arr:
        sums = sums | {s + x for s in sums}
    return sorted(sums)

This is equivalent to iterating over all 2^k subsets using bitmasks, but the set-based approach is cleaner and naturally deduplicates identical sums. The result is a sorted list of all achievable subset sums. You can also enumerate using a bitmask loop, which is sometimes faster for small arrays because it avoids the overhead of set operations.

2. Binary search for the closest value

Once you have a sorted list of candidate values, finding the one closest to a target is a standard binary search pattern. Use bisect_left to find the insertion point, then compare the elements on both sides:

from bisect import bisect_left

def closest_in_sorted(arr, target):
    idx = bisect_left(arr, target)
    best = float("inf")
    if idx < len(arr):
        best = min(best, abs(arr[idx] - target))
    if idx > 0:
        best = min(best, abs(arr[idx - 1] - target))
    return best

You must check both arr[idx] and arr[idx - 1] because bisect_left gives you the first element that is not less than the target. The closest value could be either the one at the insertion point or the one just before it.

Edge cases

• All elements are zero: Every subset sums to 0. The answer is abs(goal).
• Goal is zero: The empty subset always sums to 0, so the answer is at most 0. It will always be exactly 0.
• Single element: You either pick it or skip it. The answer is min(abs(goal), abs(goal - nums[0])).
• All elements are positive: Subset sums range from 0 to sum(nums). If goal is negative, the answer is abs(goal).
• Large negative elements: Subset sums can be very negative. The binary search still works correctly because both lists are sorted.
• n = 1: Only two subsets exist (empty and the single element). Handle it normally; the algorithm works without special-casing.

From understanding to recall

The meet-in-the-middle pattern has a clear trigger: the input size is too large for full enumeration but small enough when halved. For this problem, n up to 40 is the signal. Whenever you see a constraint around 30 to 50 that involves subset enumeration, think "split in half."

The implementation has three distinct phases: enumerate left sums, enumerate right sums, and binary search for the best pair. Practice writing each phase independently. The subset sum generation is a reusable building block that appears in knapsack variants and other combinatorial problems. The binary search for closest value is a standard pattern you will use in dozens of problems.

Spaced repetition is especially valuable for meet-in-the-middle problems because they appear less frequently than, say, two-pointer or sliding-window problems. That infrequency makes them easy to forget. By drilling the pattern at increasing intervals, you keep it ready for the rare but important moments when it comes up.

Related posts

• Combination Sum - Subset exploration with backtracking
• Subsets - Generating all subsets of an array
• Split Array Largest Sum - Another problem about splitting arrays optimally

Meet in the middle is one of those techniques that feels like magic the first time you see it. You split an impossible problem into two manageable pieces, combine them with binary search, and suddenly a trillion-subset problem runs in milliseconds. CodeBricks breaks this pattern into its reusable components and drills them until the technique is second nature.