Meet-in-the-Middle

Why Meet-in-the-Middle Matters

Suppose a list of adjustments contains positive and negative amounts, and you want to know how many subsets total exactly a requested amount. With forty entries there are $2^{40}$ index subsets, over a trillion possibilities. A direct exhaustive search is often too large, while a dynamic program indexed by sum may be impractical when the numbers themselves are large.

Meet-in-the-middle changes the shape of the search. Split the entries into two disjoint halves, summarize the subsets of each half, and find compatible summaries efficiently. For subset sum, compatibility is especially simple: if the left sum is $s$, the right sum must be $T-s$. Each twenty-entry half has $2^{20}$ subsets, about a million. The algorithm avoids inspecting every pair of half-subsets by using a sorted index or a hash table.

This is a general technique rather than one fixed problem. It works when a complete candidate decomposes into independent partial choices with an efficient compatibility test. This lesson implements exact signed subset-sum counting, including duplicate values, one deterministic witness, explicit recursive undo, and optional safe interval pruning. The pruning is an extra optimization; the main exponential saving comes from splitting and indexing the join.

Core Concepts and Terminology

Given indexed integers $v_0,\ldots,v_{n-1}$ and target $T$, compute

$$C(T)=\#\left\{S\subseteq\{0,\ldots,n-1\}:\sum_{i\in S}v_i=T\right\}.$$

Subsets are distinguished by indices. For [2,2] and target 2, there are two solutions, one using each position. The empty subset is included and has sum zero. Negative numbers and zeros are allowed. An empty array therefore has count one for target zero and count zero for every other target.

Let $a=\lceil n/2\rceil$ and $b=\lfloor n/2\rfloor$. The left half contains original indices $0$ through $a-1$, and the right half contains indices $a$ through $n-1$. A full subset decomposes uniquely into a left subset and a right subset:

$$\sum_{i\in S}v_i=s_L+s_R,\qquad s_L+s_R=T\iff s_R=T-s_L.$$

The program stores the smaller right half's summaries and streams the left search. A local bitmask identifies selected positions within its half. Bit $i$ of a full mask identifies original index $i$, and the masks combine as

$$m_{\mathrm{full}}=m_L+2^a m_R.$$

The bit ranges are disjoint, so the code can use bitwise OR after shifting instead of addition. A right group stores three values: its sum, the number of right masks giving that sum, and the smallest such mask. The answer includes the total count and the matching full subset with the smallest numeric full mask. This policy does not mean minimum cardinality or lexicographically smallest list of indices.

For optional pruning, define the minimum possible contribution of undecided entries as the sum of their negative values, and the maximum as the sum of their positive values. Add those to the current left sum and to the analogous right-half extrema. If the target lies outside this interval, no completion can match it. An interval can contain unattainable sums, so being inside it is only permission to keep searching, not proof of a match.

The diagram uses left values [3,-2,5], right values [4,-1,2], and target 9. The left search decides higher local bit positions first, excludes before including, and visits completed masks in increasing numeric order. It can prune a whole subtree whose maximum possible total is seven. Every right subset is still generated; meet-in-the-middle does not inherently require pruning either search.

How Meet-in-the-Middle Works, Step by Step

The implementations follow the same five stages.

1. Split without reordering. Copy the input and put its first $a$ entries on the left. Build left prefix arrays low[k] and high[k]: the sums of negative and positive values, respectively, among left positions $0,\ldots,k-1$.
2. Generate every right subset. Start with sum zero and mask zero. At position pos, recurse first without the entry. Then add its value, set its bit, recurse, and undo both changes. At pos=-1, append a copied (sum,mask) record. The empty right half also produces one record, (0,0).
3. Sort and group. Sort right records by sum, then numeric mask. Combine each equal-sum run into (sum,frequency,minimum_mask). Sorting masks within the run makes its first mask the minimum. Discard the ungrouped records after compression; peak storage still includes their generation and sorting.
4. Search the left half. Use the same exclude-first, include-second recursion and explicit undo. Before branching or joining, optionally check the achievable-total interval. At a surviving complete left subset, binary-search the grouped right sums for its complement.
5. Accumulate and reconstruct. If the group exists, add its entire frequency to the answer. Combine the left mask with the group's minimum right mask and retain the smaller full witness mask. Finish every remaining left branch because the task counts all solutions. Decode the saved full mask into increasing original indices.

More precisely, if positions $0$ through pos remain undecided, the current left sum is $s$, and the right extrema are $r_{\min}$ and $r_{\max}$, then every possible full completion lies in

$$\left[s+\mathrm{low}[\mathrm{pos}+1]+r_{\min},\quad s+\mathrm{high}[\mathrm{pos}+1]+r_{\max}\right].$$

Reject only when $T$ lies strictly outside that interval. At a complete left subset, pos=-1 and both prefix contributions are zero. The check then rejects complements outside the right sum range. Complements inside the range can still be absent, so the binary-search equality check remains essential.

The local sum and mask are restored after an include branch, including a branch that was pruned. The accumulated count and best witness are global results and are retained. Bit clearing uses XOR only because the recursion sets a previously unset bit exactly once and removes it exactly once on return.

The binary search returns the first group whose sum is at least the complement. If that position is past the end or the sum is unequal, this left subset contributes zero. Otherwise it contributes exactly the group's frequency. There is no loop over individual matching right masks and no Cartesian-product enumeration.

flowchart TD
    A["Validate and split input; build left interval prefixes"] --> B["Generate all right sum-mask records with undo"]
    B --> C["Sort records; group by sum with frequency and minimum mask"]
    C --> D["Enter left search; count node"]
    D --> E{"Pruning enabled and target outside completion interval?"}
    E -->|Yes| F["Count prune; return"]
    E -->|No| G{"All left decisions fixed?"}
    G -->|Yes| H["Binary-search the complement T minus left sum"]
    H --> I{"Equal-sum group exists?"}
    I -->|Yes| J["Add its frequency; minimize full witness mask"]
    I -->|No| K["Return with zero added"]
    J --> K
    G -->|No| L["Recurse excluding current position"]
    L --> M["Add value and set bit; recurse including position"]
    M --> N["Clear bit and subtract value; return"]

Worked Example with a Full Trace

Take values [3,-2,5,4,-1,2] and target $T=9$. The left half is [3,-2,5] and the right half is [4,-1,2]. For three-bit masks, write the highest bit on the left: right mask 001 selects value 4, while right mask 110 selects values $-1$ and 2.

The right generator visits all fifteen nodes of its depth-three binary decision tree and emits these eight leaves in numeric mask order:

After sorting, the sum groups are (-1,1,2), (0,1,0), (1,1,6), (2,1,4), (3,1,3), (4,1,1), (5,1,7), (6,1,5), written as (sum,frequency,minimum_mask). The right minimum is $-1$ and maximum is 6. Left prefix arrays are low=[0,0,-2,-2] and high=[0,3,3,8].

At the left root, the full completion interval is $[-3,14]$. Exclude left index 2, value 5, leaving interval $[-3,9]$. If index 1, value $-2$, is also excluded, deciding index 0 yields either left sum 0 or 3. Sum 0 has full interval $[-1,6]$ and is pruned; sum 3 needs right sum 6 and contributes one solution. Including $-2$ while 5 is excluded instead produces interval $[-3,7]$ before deciding index 0. Prune that entire subtree, removing left masks 010 and 011 without visiting their leaves.

The include-index-2 subtree has no interval prune. Its four complete left sums are 5, 8, 3, and 6. Each has one right complement. The complete left-search trace follows; pos identifies the next undecided left position, and a dash means no lookup was performed. Count and witness mask are cumulative after the listed event.

The five matching joins, including the first match from the exclude-index-2 subtree, are:

Every group frequency is one here, so the count is five. The smallest full mask is 12, which selects values 5 and 4 at original indices [2,3]. The first match, mask 41, is valid but is not the requested minimum-mask witness.

Each of the five binary searches over eight groups makes three midpoint comparisons, for fifteen total. Right generation visits fifteen nodes; the left search visits thirteen, including the two prune calls. Hence the total node statistic is 28. With interval pruning disabled, all fifteen left nodes and all eight left leaves are processed, yielding thirty nodes, eight lookups, and twenty-four midpoint comparisons, with the same count and witness.

Implementation in Python, C++, and Java

Each panel is a complete runnable program with the same split, record sort order, grouped metadata, recursion order, interval pruning, binary-search rule, and witness policy. The input is a non-null sequence of integers. At most forty entries are accepted; each entry is in $[-10^9,10^9]$, and the target is in $[-10^{12},10^{12}]$. Python rejects noninteger inputs rather than coercing them. Construction copies the input without sorting or deduplicating its entries.

C++ and Java use signed 64-bit arithmetic for sums, targets, masks, frequencies, counts, and statistics. Absolute full subset sums are at most $40\cdot10^9$, complements remain within their 64-bit range, masks use at most forty bits, and counts are at most $2^{40}$. The shift expressions use 1LL in C++ and 1L in Java. Raising the item limit requires reconsidering both integer widths and exponentially growing storage.

generate records every right subset with explicit sum and mask changes and their undo. search streams the left subsets, optionally pruning complete or partial states. The largest right table can contain $2^{20}$ records before grouping. Equal-sum compression reduces the number of groups searched, but does not avoid generating those records or change peak exponential space complexity. Language object overhead matters at the upper limit.

solve resets working tables, results, statistics, sum, and mask on every call. Both the pruned and unpruned modes can be run repeatedly on the same object. After each half-search the sum and mask must be zero again. The returned witness is a copied list of original indices. An empty witness can mean either no solution or a valid empty subset, so always consult the count. For target zero, the empty subset is always one of the counted solutions.

The eight printed statistics are:

• nodes: right generation calls plus left search calls.
• right_nodes: all calls in the complete right enumeration tree, including leaves.
• left_nodes: left calls, including prunes and completed subsets.
• pruned: left calls rejected by the optional interval test, before any lookup.
• lookups: surviving complete left subsets submitted to the complement search.
• comparisons: midpoint comparisons inside binary search; the final equality check is excluded.
• records: number of generated right subset records, $2^b$.
• groups: number of distinct right sums after frequency compression.

The last two are table sizes rather than search counters. The programs do not count sort comparisons in comparisons. restored=YES refers to the mutable half-search sum and mask, not to erasing accumulated counts or the grouped right index.

class SubsetMITM:
    def __init__(self, values, target):
        if len(values) > 40 or type(target) is not int or not -10**12 <= target <= 10**12:
            raise ValueError("invalid size or target")
        if any(type(v) is not int or not -10**9 <= v <= 10**9 for v in values):
            raise ValueError("invalid value")
        self.values, self.target = list(values), target
        self.a = (len(values) + 1) // 2
        self.left, self.right = self.values[:self.a], self.values[self.a:]
        self.low, self.high = [0], [0]
        for v in self.left:
            self.low.append(self.low[-1] + min(0, v))
            self.high.append(self.high[-1] + max(0, v))

    def generate(self, pos):
        self.right_nodes += 1
        if pos < 0:
            self.records.append((self.partial, self.mask))
            return
        self.generate(pos - 1)
        self.partial += self.right[pos]
        self.mask |= 1 << pos
        self.generate(pos - 1)
        self.mask ^= 1 << pos
        self.partial -= self.right[pos]

    def lower_bound(self, need):
        lo, hi = 0, len(self.groups)
        while lo < hi:
            mid = (lo + hi) // 2
            self.comparisons += 1
            if self.groups[mid][0] < need:
                lo = mid + 1
            else:
                hi = mid
        return lo

    def search(self, pos):
        self.left_nodes += 1
        lower = self.partial + self.low[pos + 1] + self.groups[0][0]
        upper = self.partial + self.high[pos + 1] + self.groups[-1][0]
        if self.prune and (self.target < lower or self.target > upper):
            self.pruned += 1
            return
        if pos < 0:
            self.lookups += 1
            need = self.target - self.partial
            at = self.lower_bound(need)
            if at < len(self.groups) and self.groups[at][0] == need:
                _, frequency, right_mask = self.groups[at]
                self.count += frequency
                candidate = self.mask | (right_mask << self.a)
                if self.best_mask < 0 or candidate < self.best_mask:
                    self.best_mask = candidate
            return
        self.search(pos - 1)
        self.partial += self.left[pos]
        self.mask |= 1 << pos
        self.search(pos - 1)
        self.mask ^= 1 << pos
        self.partial -= self.left[pos]

    def solve(self, prune=True):
        if type(prune) is not bool:
            raise ValueError("prune must be Boolean")
        self.prune = prune
        self.records, self.groups = [], []
        self.partial = self.mask = 0
        self.right_nodes = self.left_nodes = self.pruned = 0
        self.lookups = self.comparisons = self.count = 0
        self.best_mask = -1
        self.generate(len(self.right) - 1)
        if self.partial != 0 or self.mask != 0:
            raise RuntimeError("right undo failed")
        record_count = len(self.records)
        self.records.sort()
        for total, mask in self.records:
            if self.groups and self.groups[-1][0] == total:
                self.groups[-1][1] += 1
            else:
                self.groups.append([total, 1, mask])
        self.records.clear()
        self.search(len(self.left) - 1)
        if self.partial != 0 or self.mask != 0:
            raise RuntimeError("left undo failed")
        witness = [i for i in range(len(self.values))
                   if self.best_mask >= 0 and (self.best_mask >> i) & 1]
        stats = [self.right_nodes + self.left_nodes, self.right_nodes, self.left_nodes,
                 self.pruned, self.lookups, self.comparisons, record_count, len(self.groups)]
        return self.count, witness, stats


def show(name, values, target, prune=True):
    count, witness, stats = SubsetMITM(values, target).solve(prune)
    print(f"{name}: count={count}, witness=[" + ",".join(map(str, witness)) + "]")
    labels = ("nodes", "right_nodes", "left_nodes", "pruned", "lookups", "comparisons", "records", "groups")
    print(", ".join(f"{k}={v}" for k, v in zip(labels, stats)) + ", restored=YES")


def main():
    show("worked", [3, -2, 5, 4, -1, 2], 9)
    show("no pruning", [3, -2, 5, 4, -1, 2], 9, False)
    show("duplicates", [2, 2, 2, 2], 4)
    show("negative rescue", [8, -5], 3)
    show("missing", [4, 10, 6, 12], 9)
    show("zeros", [0, 0, 0, 0], 0)
    show("empty", [], 0)
    show("outside range", [1, 2, 3, 4], 100)
    print("checks = PASS")


if __name__ == "__main__":
    main()

#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
using namespace std;

struct Entry { long long sum, mask; };
struct Group { long long sum, frequency, mask; };
struct Result { long long count; vector<int> witness; vector<long long> stats; };

class SubsetMITM {
public:
    vector<long long> values,left,right,low,high;
    long long target,partial=0,mask=0,count=0,best_mask=-1;
    int a;
    bool prune=true;
    vector<Entry> records;
    vector<Group> groups;
    long long right_nodes=0,left_nodes=0,pruned=0,lookups=0,comparisons=0;

    SubsetMITM(const vector<long long>& input,long long t) : values(input),target(t) {
        if (values.size()>40 || target < -1000000000000LL || target > 1000000000000LL)
            throw invalid_argument("invalid size or target");
        for (long long v:values)
            if (v < -1000000000LL || v > 1000000000LL) throw invalid_argument("invalid value");
        a=static_cast<int>((values.size()+1)/2);
        left.assign(values.begin(),values.begin()+a); right.assign(values.begin()+a,values.end());
        low.push_back(0); high.push_back(0);
        for (long long v:left) { low.push_back(low.back()+min(0LL,v)); high.push_back(high.back()+max(0LL,v)); }
    }
    void generate(int pos) {
        ++right_nodes;
        if (pos<0) { records.push_back({partial,mask}); return; }
        generate(pos-1);
        partial+=right[pos]; mask|=1LL<<pos;
        generate(pos-1);
        mask^=1LL<<pos; partial-=right[pos];
    }
    size_t lower_bound_sum(long long need) {
        size_t lo=0,hi=groups.size();
        while (lo<hi) {
            size_t mid=lo+(hi-lo)/2; ++comparisons;
            if (groups[mid].sum<need) lo=mid+1; else hi=mid;
        }
        return lo;
    }
    void search(int pos) {
        ++left_nodes;
        long long lower=partial+low[pos+1]+groups.front().sum;
        long long upper=partial+high[pos+1]+groups.back().sum;
        if (prune && (target<lower || target>upper)) { ++pruned; return; }
        if (pos<0) {
            ++lookups; long long need=target-partial; size_t at=lower_bound_sum(need);
            if (at<groups.size() && groups[at].sum==need) {
                count+=groups[at].frequency;
                long long candidate=mask|(groups[at].mask<<a);
                if (best_mask<0 || candidate<best_mask) best_mask=candidate;
            }
            return;
        }
        search(pos-1);
        partial+=left[pos]; mask|=1LL<<pos;
        search(pos-1);
        mask^=1LL<<pos; partial-=left[pos];
    }
    Result solve(bool use_pruning=true) {
        prune=use_pruning; records.clear(); groups.clear(); partial=mask=count=0; best_mask=-1;
        right_nodes=left_nodes=pruned=lookups=comparisons=0;
        generate(static_cast<int>(right.size())-1);
        if (partial!=0 || mask!=0) throw logic_error("right undo failed");
        long long record_count=static_cast<long long>(records.size());
        sort(records.begin(),records.end(),[](const Entry& x,const Entry& y) {
            return x.sum!=y.sum ? x.sum<y.sum : x.mask<y.mask;
        });
        for (const Entry& e:records) {
            if (!groups.empty() && groups.back().sum==e.sum) ++groups.back().frequency;
            else groups.push_back({e.sum,1,e.mask});
        }
        vector<Entry>().swap(records);
        search(static_cast<int>(left.size())-1);
        if (partial!=0 || mask!=0) throw logic_error("left undo failed");
        vector<int> witness;
        if (best_mask>=0)
            for (int i=0;i<static_cast<int>(values.size());++i) if ((best_mask>>i)&1LL) witness.push_back(i);
        return {count,witness,{right_nodes+left_nodes,right_nodes,left_nodes,pruned,
                              lookups,comparisons,record_count,static_cast<long long>(groups.size())} };
    }
};

void show(const string& name,const vector<long long>& values,long long target,bool prune=true) {
    Result r=SubsetMITM(values,target).solve(prune);
    cout<<name<<": count="<<r.count<<", witness=[";
    for (size_t i=0;i<r.witness.size();++i) { if(i) cout<<','; cout<<r.witness[i]; }
    cout<<"]\n";
    vector<string> labels={"nodes","right_nodes","left_nodes","pruned","lookups","comparisons","records","groups"};
    for (size_t i=0;i<labels.size();++i) { if(i) cout<<", "; cout<<labels[i]<<'='<<r.stats[i]; }
    cout<<", restored=YES\n";
}
int main() {
    show("worked",{3,-2,5,4,-1,2},9);
    show("no pruning",{3,-2,5,4,-1,2},9,false);
    show("duplicates",{2,2,2,2},4);
    show("negative rescue",{8,-5},3);
    show("missing",{4,10,6,12},9);
    show("zeros",{0,0,0,0},0);
    show("empty",{},0);
    show("outside range",{1,2,3,4},100);
    cout<<"checks = PASS\n";
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static final class Entry {
        long sum,mask;
        Entry(long sum,long mask) { this.sum=sum; this.mask=mask; }
    }
    static final class Group {
        long sum,frequency,mask;
        Group(long sum,long frequency,long mask) { this.sum=sum; this.frequency=frequency; this.mask=mask; }
    }
    static final class Result {
        long count;
        List<Integer> witness;
        long[] stats;
        Result(long count,List<Integer> witness,long[] stats) {
            this.count=count; this.witness=new ArrayList<>(witness); this.stats=stats.clone();
        }
    }
    static final class SubsetMITM {
        long[] values,left,right,low,high;
        long target,partial,mask,count,bestMask;
        int a;
        boolean prune;
        List<Entry> records=new ArrayList<>();
        List<Group> groups=new ArrayList<>();
        long rightNodes,leftNodes,pruned,lookups,comparisons;

        SubsetMITM(long[] input,long target) {
            if(input.length>40 || target < -1_000_000_000_000L || target>1_000_000_000_000L)
                throw new IllegalArgumentException("invalid size or target");
            for(long v:input)
                if(v < -1_000_000_000L || v>1_000_000_000L) throw new IllegalArgumentException("invalid value");
            values=input.clone(); this.target=target; a=(values.length+1)/2;
            left=Arrays.copyOfRange(values,0,a); right=Arrays.copyOfRange(values,a,values.length);
            low=new long[a+1]; high=new long[a+1];
            for(int i=0;i<a;++i) { low[i+1]=low[i]+Math.min(0,left[i]); high[i+1]=high[i]+Math.max(0,left[i]); }
        }
        void generate(int pos) {
            ++rightNodes;
            if(pos<0) { records.add(new Entry(partial,mask)); return; }
            generate(pos-1);
            partial+=right[pos]; mask|=1L<<pos;
            generate(pos-1);
            mask^=1L<<pos; partial-=right[pos];
        }
        int lowerBound(long need) {
            int lo=0,hi=groups.size();
            while(lo<hi) {
                int mid=lo+(hi-lo)/2; ++comparisons;
                if(groups.get(mid).sum<need) lo=mid+1; else hi=mid;
            }
            return lo;
        }
        void search(int pos) {
            ++leftNodes;
            long lower=partial+low[pos+1]+groups.get(0).sum;
            long upper=partial+high[pos+1]+groups.get(groups.size()-1).sum;
            if(prune && (target<lower || target>upper)) { ++pruned; return; }
            if(pos<0) {
                ++lookups; long need=target-partial; int at=lowerBound(need);
                if(at<groups.size() && groups.get(at).sum==need) {
                    Group g=groups.get(at); count+=g.frequency;
                    long candidate=mask|(g.mask<<a);
                    if(bestMask<0 || candidate<bestMask) bestMask=candidate;
                }
                return;
            }
            search(pos-1);
            partial+=left[pos]; mask|=1L<<pos;
            search(pos-1);
            mask^=1L<<pos; partial-=left[pos];
        }
        Result solve(boolean usePruning) {
            prune=usePruning; records=new ArrayList<>(); groups=new ArrayList<>(); partial=mask=count=0; bestMask=-1;
            rightNodes=leftNodes=pruned=lookups=comparisons=0;
            generate(right.length-1);
            if(partial!=0 || mask!=0) throw new IllegalStateException("right undo failed");
            long recordCount=records.size();
            records.sort((x,y)->x.sum!=y.sum ? Long.compare(x.sum,y.sum) : Long.compare(x.mask,y.mask));
            for(Entry e:records) {
                if(!groups.isEmpty() && groups.get(groups.size()-1).sum==e.sum) ++groups.get(groups.size()-1).frequency;
                else groups.add(new Group(e.sum,1,e.mask));
            }
            records.clear();
            search(left.length-1);
            if(partial!=0 || mask!=0) throw new IllegalStateException("left undo failed");
            List<Integer> witness=new ArrayList<>();
            if(bestMask>=0) for(int i=0;i<values.length;++i) if(((bestMask>>i)&1L)!=0) witness.add(i);
            return new Result(count,witness,new long[] {rightNodes+leftNodes,rightNodes,leftNodes,pruned,
                              lookups,comparisons,recordCount,groups.size()});
        }
    }
    static void show(String name,long[] values,long target,boolean prune) {
        Result r=new SubsetMITM(values,target).solve(prune);
        StringBuilder out=new StringBuilder(name+": count="+r.count+", witness=[");
        for(int i=0;i<r.witness.size();++i) { if(i>0) out.append(','); out.append(r.witness.get(i)); }
        System.out.println(out+"]"); out=new StringBuilder();
        String[] labels={"nodes","right_nodes","left_nodes","pruned","lookups","comparisons","records","groups"};
        for(int i=0;i<labels.length;++i) { if(i>0) out.append(", "); out.append(labels[i]).append('=').append(r.stats[i]); }
        System.out.println(out+", restored=YES");
    }
    public static void main(String[] args) {
        show("worked",new long[] {3,-2,5,4,-1,2},9,true);
        show("no pruning",new long[] {3,-2,5,4,-1,2},9,false);
        show("duplicates",new long[] {2,2,2,2},4,true);
        show("negative rescue",new long[] {8,-5},3,true);
        show("missing",new long[] {4,10,6,12},9,true);
        show("zeros",new long[] {0,0,0,0},0,true);
        show("empty",new long[] {},0,true);
        show("outside range",new long[] {1,2,3,4},100,true);
        System.out.println("checks = PASS");
    }
}

Expected stdout, identical in all three languages:

• worked: count=5, witness=[2,3]
• nodes=28, right_nodes=15, left_nodes=13, pruned=2, lookups=5, comparisons=15, records=8, groups=8, restored=YES
• no pruning: count=5, witness=[2,3]
• nodes=30, right_nodes=15, left_nodes=15, pruned=0, lookups=8, comparisons=24, records=8, groups=8, restored=YES
• duplicates: count=6, witness=[0,1]
• nodes=14, right_nodes=7, left_nodes=7, pruned=0, lookups=4, comparisons=8, records=4, groups=3, restored=YES
• negative rescue: count=1, witness=[0,1]
• nodes=6, right_nodes=3, left_nodes=3, pruned=1, lookups=1, comparisons=2, records=2, groups=2, restored=YES
• missing: count=0, witness=[]
• nodes=12, right_nodes=7, left_nodes=5, pruned=1, lookups=2, comparisons=5, records=4, groups=4, restored=YES
• zeros: count=16, witness=[]
• nodes=14, right_nodes=7, left_nodes=7, pruned=0, lookups=4, comparisons=4, records=4, groups=1, restored=YES
• empty: count=1, witness=[]
• nodes=2, right_nodes=1, left_nodes=1, pruned=0, lookups=1, comparisons=1, records=1, groups=1, restored=YES
• outside range: count=0, witness=[]
• nodes=8, right_nodes=7, left_nodes=1, pruned=1, lookups=0, comparisons=0, records=4, groups=4, restored=YES
• checks = PASS

The negative rescue case demonstrates that a left partial sum above the target can still succeed: $8+(-5)=3$. The missing case has complements inside the right sum interval that are absent from its actual groups. zeros counts every one of the sixteen index subsets, while retaining the empty witness. outside range prunes the left root only after the right table has been built; this implementation does not perform a global interval rejection before enumeration.

Validation covered 8,743 inputs per language with pruning disabled and enabled, for 17,486 mode/input cases per language, including five invalid inputs. The valid corpus contains every ordered array of lengths zero through four over $\{-2,-1,0,1,2\}$ with targets from $-4$ through 4; 1,500 seeded random signed instances; 200 large-integer instances; and boundary fixtures, including forty zeros. There were 4,427 inputs with at least one solution and 4,311 with none. Independent full-subset sum tables checked counts and minimum-mask witnesses for small inputs; the forty-zero count was checked against $2^{40}=1{,}099{,}511{,}627{,}776$. An immutable reference model also checked all statistics. Repeated solves returned identical results and preserved input data.

Instrumented small-instance checks verified 485,540 right-search restorations, 467,468 left-search restorations and interval/group invariants, 220,754 lower-bound positions, and 30,454 safe prune decisions. Each prune was checked against the exact remaining subset sums to establish that it discarded zero matches. Pruning reduced total visits on 5,960 valid inputs. C++ ran with address and undefined-behavior sanitizers; Java ran with assertions enabled. The large boundary fixture was checked separately without the per-node instrumentation.

Complexity, Correctness, and Invariants

Let $a=\lceil n/2\rceil$, $b=\lfloor n/2\rfloor$, $L=2^a$, and $R=2^b$. Let $g\le R$ be the number of distinct right sums, $P$ the number of left recursive calls actually visited, and $q$ the number of completed left subsets queried. Then $P\le2L-1$ and $q\le L$.

Right generation visits exactly $2R-1$ nodes and takes $O(R)$ time because each include/undo changes the sum and mask in constant time. It does not rescan all selected values at each leaf. Comparison sorting costs $O(R\log(R+1))$ in the worst case, and grouping takes $O(R)$. Prefix intervals take $O(n)$ to build. Each left call performs a constant-time interval check, and each surviving leaf performs $O(\log(g+1))$ binary-search work. Witness decoding costs $O(n)$ once, after the search.

Thus the shown implementation has the deterministic upper bound

$$T=O\bigl(n+R\log(R+1)+P+q\log(g+1)\bigr),$$

which yields the conservative worst-case bound $O((n+1)2^{\lceil n/2\rceil})$. This includes the logarithmic work of the straightforward sort-and-search version. A headline description of meet-in-the-middle that hides polynomial factors must not be mistaken for the exact complexity of this code.

In the best left-search case, the root interval already excludes the target, so $P=1$ and $q=0$. The program still generates and sorts the entire right table. Its total time is therefore at least $\Omega(n+R)$, with an upper bound of $O(n+R\log(R+1))$ even when no match is possible. Favorably ordered records can make adaptive library sorting faster, but that is not a cross-language worst-case guarantee. No distribution-independent average-case pruning bound is assumed.

Peak space is $O(n+R)$ for right records, groups, sorting workspace, interval prefixes, the copied input, and the recursion path. Only one half's subset table is stored; the left half is streamed. Compression may greatly reduce $g$, but the uncompressed records have already existed. Storing or printing every full matching subset would additionally require work proportional to that output, which can be $2^n$ even when the count fits in one integer.

Correctness begins with the unique decomposition of a full subset into disjoint left and right index subsets. Right enumeration emits each right mask exactly once, including zero; grouping retains the total number of masks with each sum. Left recursion likewise visits each unpruned left mask once. For a completed left mask, exactly the right masks with sum $T-s_L$ produce solutions, so adding their frequency counts each full solution once and no incompatible pair.

The optional interval bound contains every full completion: each undecided negative value contributes no less than that value, each positive contributes no more than itself, and the right extrema cover every right subset. A target outside the interval has no matching pair, so pruning does not change the count. Exact undo preserves the sum-mask relationship for sibling branches.

For a fixed left mask, the full mask increases with the right mask, since its right bits occupy disjoint higher positions. The minimum right mask in the matching group therefore gives the smallest full witness for that left choice. Taking the minimum of these candidates over all matching left masks yields the globally smallest numeric full mask. This witness metadata is separate from the frequency used for counting.

Variants, Pitfalls, and Optimizations

Do not undo the exponential saving at the join. Splitting alone is insufficient. Explicitly testing all $L\cdot R=2^n$ pairs returns to full exponential work. Use complement lookup, two pointers on sorted lists, or another indexed compatibility test. Keep the split close to balanced; an extreme split leaves one enumeration almost as large as the original problem.

Duplicates and empty subsets. A set of distinct sums is enough for a decision question, but loses information needed for counting. Keep frequencies, and keep at least one representative if a witness is required. Empty half-subsets allow solutions that lie entirely in the other half. Removing them would also break empty-input and target-zero cases.

Signed values and optional pruning. The rule “current sum exceeds target, so stop” is valid only with suitable restrictions on future contributions. Here a negative value in either half may bring the total back down. Use the full interval that includes all undecided left entries and the stored right half, and use strict outside tests. Being inside the interval does not prove attainability; for example, right sums 0 and 2 do not provide sum 1.

Two sorted lists and faster construction. If both halves are stored in increasing sum order, scan one from the start and the other from the end. Advance the left pointer when the combined sum is too small and the right pointer when it is too large. On equality, multiply the two matching run frequencies and skip both runs. To construct a sorted half-list without comparison-sorting it afterward, begin with [0]; for each value $v$, merge the current sorted list with its copy shifted by $v$. A uniform shift preserves order even when $v$ is negative. The total merge work over all doubling stages is linear in the final list size. With appropriate metadata and a linear two-pointer join, this gives the familiar $O(L+R)$ time version, while storing both half-lists. The supplied code uses DFS, sorting, and binary search to make explicit undo and one-sided storage easy to inspect.

Hashing. A map from right sum to frequency and minimum mask can avoid sorting and group records during generation. This often gives expected linear work in the number of half-subsets, but its worst-case and memory behavior depend on the dictionary. A count and representative must both be updated correctly. The deterministic sorted representation here makes the join and comparison counter directly auditable.

Different compatibility conditions. For an exactly-$k$ subset constraint, include cardinality in the state and match both sum and remaining cardinality. For nearest-target sum, inspect neighboring sorted sums around the complement and use an appropriate distance bound; the exact-target pruning rule cannot simply discard every interval missing the target. For subset XOR, compatibility uses XOR rather than subtraction. For a capacity/value optimization, store weight-value pairs and use a proven Pareto frontier or prefix optimum; discarding dominated entries is not automatically safe when the task counts every feasible subset.

Memory and numeric width. Peak space is exponential despite the smaller exponent. Grouping a million records into one sum group does not erase the cost of generating the million records first. Use sufficiently wide sums and masks, and count with enough precision for all $2^n$ subsets. A 32-bit shift in C++ or Java is unsuitable for a full forty-bit witness. If generating actual solutions rather than counts, include their potentially enormous output cost.

Practice Problems and Real-World Use

Start with arrays of at most a dozen entries and compare against a full subset table. Test negative values, repeated values, zeros, odd split sizes, a solution in only one half, an empty input, and a target absent from the actual sum set but inside its interval. Verify the witness's original indices are distinct and sum to the target, then independently check its stated minimum-mask policy.

A standard practice task is CSES: Meet in the Middle, which asks for subset counts with up to forty positive entries. The signed-input implementation here handles a broader numeric domain and uses a list-based sample driver, rather than that judge's input/output interface. Section 5.5 of Antti Laaksonen's Competitive Programmer's Handbook introduces the split-and-combine technique. The particular interval pruning, minimum-mask policy, and validation trace here are features of this teaching implementation.

Meet-in-the-middle is useful in small exact-combination tools when the number of choices is moderate but the numeric range makes sum-indexed DP expensive. It also appears in balanced partitioning, fixed-cardinality selection, and joins of independently generated partial solutions. The state summary must retain everything the compatibility condition needs; if later checks require cardinality, disjointness, or another constraint, a sum alone is not a sufficient summary.