Meet in the Middle

Meet in the middle reduces exponential enumeration by splitting independent choices into two balanced halves. For subset sum with n around 40, enumerating 2ⁿ full subsets is infeasible, but two lists of about 2²⁰ sums may fit. The technique is not dynamic programming: it explicitly generates possibilities, then efficiently joins compatible partial results. Our program counts index subsets whose sum equals a target, including duplicates and negative values.

Prerequisites: Arrays, sorting, binary search, exponential search. Difficulty: Advanced.

Build the idea

1. 1. Split choices without losing subsets

   Divide the array into a left half and a right half. Every full subset corresponds to exactly one subset from each half. If their sums are x and y, the target condition is x+y=T, equivalently y=T−x. Because choices from the two halves do not otherwise interact, a sorted lookup can replace the quadratic cross-product of lists.

2. 2. Generate half sums incrementally

   Begin with [0], representing the empty subset. For each value a, snapshot the OLD list size; append oldSum+a for each old entry. These are exactly subsets that include the new index, while old entries exclude it. Do not iterate over the growing size or append forever. Distinct subsets can have the same sum and must remain separate when counting.

3. 3. Walk an explicit example

   For [1,2,2,3] and target 4, left sums are [0,1,2,3] and right sums are [0,2,3,5]. Left 1 needs right 3; left 2 needs right 2. Therefore two subsets work: indices {1,4} and {2,3}. The two values 2 occur at different indices, so the {2,3} subset legitimately chooses both. Empty halves still contribute a zero sum.

   Left sum	Required right sum	Matches
   0	4	0
   1	3	1
   2	2	1
   3	1	0

4. 4. Join with multiplicity

   Sort the right sums. equal_range returns the entire block equal to T−x; its iterator difference counts all compatible right subsets. Add that count for each left subset, including repeated x values. For an all-zero array with target zero, every one of 2ⁿ subsets matches. A set would collapse multiplicities and return the wrong count.

5. 5. Estimate resources before coding

   Let h=ceil(n/2). Lists contain at most 2ʰ entries each. Incremental generation is O(2ʰ), not a separate O(n) summation per subset. Sorting and binary searching add a factor O(n). For n=40, each long-long list is about 8 MiB, but n=60 would need billions of entries. Negative values are fine because no monotone-sum pruning is used. If a target is small and values are nonnegative integers, pseudo-polynomial sum DP may be far cheaper.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll=long long;
vector<ll>sums(const vector<ll>&a,int from,int to){
    vector<ll>result{0}; // Include the empty subset.
    for(int i=from;i<to;++i){
        int oldSize=(int)result.size();
        for(int j=0;j<oldSize;++j){
            result.push_back(result[j]+a[i]);
        }
    }
    return result;
}
int main(){
    int n;
    ll target;
    if(!(cin>>n>>target)){
        return 0;
    }
    vector<ll>a(n);
    for(ll&x:a){
        cin>>x;
    }
    auto left=sums(a,0,n/2),right=sums(a,n/2,n);
    sort(right.begin(),right.end());
    ll answer=0;
    for(ll x:left){
        auto range=equal_range(right.begin(),right.end(),target-x);
        answer+=range.second-range.first; // Count all multiplicities.
    }
    cout<<answer<<'\n';
}

Complexity analysis

O(n·2^(n/2)) time with balanced halves, accounting for sorting and binary searches; O(2^(n/2)) memory. This is exponentially better than O(2ⁿ) full enumeration but still exponential, not polynomial. Input contract: 0≤n≤40, |aᵢ|≤10^9, |target|≤10^12; sums and the count up to 2^40 fit long long.

Example input and output

Read n target followed by n integers. Count all index subsets, including the empty subset, summing to target. n≤40.

Input

4 4
1 2 2 3

Output

2

The valid index subsets choose values {1,3} and {2,2}. No other subset totals 4.

Practical applications

Use for subset sum, balanced partition, knapsack joins and equation counting with roughly 30–44 independent choices. If partial states have additional attributes, sort or compress them while preserving the join rule. Bitmask DP is preferable when transitions depend on the currently visited subset rather than two independent halves.

Check your understanding

Why is joining two lists faster than pairing every partial subset?

Put it into practice

Find the largest subset sum at most T when values may be negative.