Meet-in-the-Middle: Halving the Exponent from O(2^N) to O(2^(N/2) log(2^(N/2)))

The Exponential Wall at $N = 40$ and Horowitz-Sahni (1974)

Consider the exact or closest Subset Sum problem: given $N$ signed 64-bit integers $A = [a_0, a_1, \dots, a_{N-1}]$ and a target sum $T$ (where $|a_i|, |T| \le 10^{18}$), find a subset $S \subseteq \{0, \dots, N-1\}$ whose sum $\sum_{i \in S} a_i$ equals $T$ (or is the largest sum $\le T$). Why do standard techniques fail when $N = 40$?

• Pseudo-polynomial DP ($O(N \cdot T)$): Fails catastrophically when $T = 10^{18}$ (requires exabytes of RAM).
• Exhaustive Brute Force ($O(2^N)$): At $N = 40$, $2^{40} = 1{,}099{,}511{,}627{,}776 \approx 1.1 \times 10^{12}$ states—requiring minutes of CPU time.

In 1974, Ellis Horowitz and Sartaj Sahni introduced the Meet-in-the-Middle paradigm: partition the input array $A$ into two disjoint halves of size $n_1 = \lfloor N/2 \rfloor$ and $n_2 = \lceil N/2 \rceil$:

Any subset $S \subseteq A$ uniquely decomposes into $S_L \subseteq A_L$ and $S_R \subseteq A_R$ such that $\text{sum}(S) = \text{sum}(S_L) + \text{sum}(S_R) = T$. Thus, enumerating all $2^{n_1}$ subset sums of $A_L$ into a list $L$ and all $2^{n_2}$ subset sums of $A_R$ into a list $R$ reduces Subset Sum to the classic 2-SUM problem: find $x \in L$ and $y \in R$ such that $x + y = T$ (or $x + y \le T$ is maximized)!

Production C++20 Implementation: $O(2^{N/2})$ Subset Sum via Incremental Merge & Two Pointers

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <span>
#include <vector>

// Generates all 2^k subset sums of items in strictly sorted order in O(2^k) time
// without calling std::sort, using incremental std::inplace_merge!
std::vector<std::int64_t> generate_sorted_subset_sums(std::span<const std::int64_t> items) {
    const std::size_t k = items.size();
    std::vector<std::int64_t> sums;
    sums.reserve(std::size_t{1} << k);
    sums.push_back(0);

    for (const std::int64_t x : items) {
        const std::size_t curr_sz = sums.size();
        for (std::size_t i = 0; i < curr_sz; ++i) {
            sums.push_back(sums[i] + x);
        }
        // Merge the two sorted halves [0, curr_sz) and [curr_sz, 2*curr_sz) in linear time
        if (x >= 0) {
            std::inplace_merge(sums.begin(),
                               sums.begin() + static_cast<std::ptrdiff_t>(curr_sz),
                               sums.end());
        } else {
            // Even for negative x, [curr_sz, 2*curr_sz) is still sorted ascending!
            std::inplace_merge(sums.begin(),
                               sums.begin() + static_cast<std::ptrdiff_t>(curr_sz),
                               sums.end());
        }
    }
    return sums;
}

// Finds the maximum subset sum <= target in O(2^(N/2)) time and space
std::int64_t max_subset_sum_at_most(const std::vector<std::int64_t>& nums,
                                    std::int64_t target) {
    const std::size_t n = nums.size();
    const std::size_t mid = n / 2;

    std::span<const std::int64_t> left_span(nums.data(), mid);
    std::span<const std::int64_t> right_span(nums.data() + mid, n - mid);

    const std::vector<std::int64_t> L = generate_sorted_subset_sums(left_span);
    const std::vector<std::int64_t> R = generate_sorted_subset_sums(right_span);

    std::int64_t best = std::numeric_limits<std::int64_t>::min();
    std::size_t i = 0;
    std::ptrdiff_t j = static_cast<std::ptrdiff_t>(R.size()) - 1;

    // Linear O(2^(N/2)) two-pointer sweep
    while (i < L.size() && j >= 0) {
        const std::int64_t cur = L[i] + R[static_cast<std::size_t>(j)];
        if (cur <= target) {
            if (cur > best) best = cur;
            if (best == target) return best; // Exact match early exit
            ++i;
        } else {
            --j;
        }
    }
    return best;
}