SyntaxPilot
Courses/Competitive Programming/Lesson 18

Competitive Programming · Lesson 18 of 90 · 10 min

Meet in the middle

queued

These are the notes for Competitive Programming episode 18. An original problem, Exact Budget, asks how many sets of sponsor offers add up to exactly the cost of a college fest stage. Last episode's bitmask loop tries every subset: it is right on the sample and gets Time Limit Exceeded on 40 offers, because 40 offers have 2^40 (over a trillion) subsets. A tunnel dug from both ends of a mountain shows the way out: split the offers into two halves, list every sum of each half (about a million each), sort one side, and for every left sum x count the right sums equal to S − x, the way you look a word up in a dictionary. That is meet in the middle. Then a hand trace, n = 40 in a fraction of a second, a stress test against the brute force, and three bugs with real outputs. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook: the fest sponsor puzzle

Your college fest needs a stage that costs exactly ₹10 lakh: not more, the committee won't allow leftovers. Sponsors make offers of 2, 3, 5 and 7 lakh. You take an offer whole, or not at all. How many different sets of offers add up to exactly 10?

  • 3 + 7 = 10
  • 2 + 3 + 5 = 10

Two ways. Easy for four sponsors. But a big fest has forty sponsors, and forty offers make 2^40 ≈ 1.1·10^12 sets: over a trillion.

Words you need first

  • A subset is any choice of items where each item is either in or out, and order does not matter. From {2, 3, 5, 7}, {3, 7} is a subset, and {7, 3} is the same subset. The empty choice {} is a subset too. n items have 2^n subsets (2 choices per item).
  • A subset sum is the total of the items in a subset. The subset {2, 3, 5} has sum 10; the empty subset has sum 0.
  • A bitmask (episode 17) is an integer whose bits say which items are in: bit i = 1 means item i is chosen. For 4 items, mask = 6 is binary 0110: items 1 and 2 are in, so with a = {2, 3, 5, 7} it is the subset {3, 5}.
  • Exponential complexity means the work grows like 2^n: every extra item doubles it. 2^20 ≈ 10^6 is fine; 2^40 ≈ 10^12 is not.

The problem: Exact Budget

Problem R · Exact Budget (written for this course). You are given n offers a[0 … n − 1] and a target S. Count the subsets of offers whose sum is exactly S.

1 ≤ n ≤ 40, 1 ≤ a[i] ≤ 10^9, 1 ≤ S ≤ 4·10^10.

Input: n and S on the first line, then the n offers. Output: one number, the count.

Sample input Sample output Why
4 10
2 3 5 7
2 {3, 7} and {2, 3, 5}

A sum can reach 40 · 10^9 = 4·10^10, far beyond the largest int (about 2.1·10^9), so every sum must be a long long. The answer itself can also be huge (see n = 40 below), so it is a long long too.

Brute force: every mask (Time Limit Exceeded)

Every number from 0 to 2^n − 1 is one subset. Add up the ticked items and compare with S.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll S;
    cin >> n >> S;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    ll ans = 0;
    for (ll mask = 0; mask < (1LL << n); mask++) {
        ll sum = 0;
        for (int i = 0; i < n; i++)
            if (mask >> i & 1) sum += a[i];
        if (sum == S) ans++;
    }
    cout << ans << "\n";
    return 0;
}
Input Output
the sample (4 10 / 2 3 5 7) 2
40 400 / 1 2 3 … 40 Time Limit Exceeded (2^40 masks × 40 steps ≈ 4.4·10^13)

Rule of thumb: plain masks are fine up to n ≈ 20.

The idea: dig the tunnel from both ends

Building a mountain tunnel In our problem
One team digs 2 km: takes 20 months one huge search over all 2^n subsets
Two teams, 1 km each, from both ends two halves of n/2 items: 2^(n/2) sums each
They meet in the middle, and the tunnel is done match left + right = S with a fast lookup

For a tunnel, two teams halve the time. For us it is far better than half, because the work is exponential: 2^40 ≈ 10^12, but 2 · 2^20 ≈ 2·10^6.

The split observation

  1. Split the array: L = the first n/2 items, R = the rest.
  2. Every subset of all items = (a subset of L) + (a subset of R). The two choices are independent choices: what you pick on the left does not limit what you can pick on the right. Example: {2, 3, 5} = {2, 3} from the left + {5} from the right.
  3. List all 2^(n/2) sums of each half.
  4. If the left part sums to x, the right part must sum to exactly S − x. So for each left sum x, count how many right sums equal S − x, and add them up.

We never multiply the halves together (that would be 2^20 × 2^20 = 2^40 again). We only match them.

Listing every subset sum of a half

Start with just {0} (the empty choice). For each new item x, copy every sum so far with x added. Each item doubles the list.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> sums(vector<ll> v) {
    vector<ll> s = {0};
    for (ll x : v) {
        int m = s.size();
        for (int i = 0; i < m; i++) s.push_back(s[i] + x);
    }
    return s;
}

int main() {
    vector<ll> left = {2, 3}, right = {5, 7};
    for (ll x : sums(left)) cout << x << " ";
    cout << "<- left sums\n";
    for (ll x : sums(right)) cout << x << " ";
    cout << "<- right sums\n";
    return 0;
}

Real output:

0 2 3 5 <- left sums
0 5 7 12 <- right sums

Four sums per half: 2^2. For {2, 3}: start {0} → add 2 → {0, 2} → add 3 → {0, 2, 3, 5}.

Why int m = s.size(); first? Because push_back makes s grow during the loop; we must only copy the sums that existed before this item.

Hand trace on the sample

S = 10, left {2, 3}, right {5, 7}. Right sums sorted: 0 5 7 12.

Left sum x Need S − x Found in right sums? Subset
0 10 no (0 matches)
2 8 no (0 matches)
3 7 yes (1 match) {3} + {7}
5 5 yes (1 match) {2, 3} + {5}

Total: 2, the same two subsets as before.

The fast lookup: a dictionary

A paper dictionary In code
Words are in alphabetical order: that's why lookup is fast sorting: sort(Bs.begin(), Bs.end()), once
Open in the middle, go left or right, halving the pages binary search (episode 11): about log2(m) steps, 20 for a million
The same word can have several meanings: count all of them equal_range: the first and last-plus-one position of a value
  • Sorting puts values in increasing order: 7 0 12 5 → 0 5 7 12. std::sort takes O(m log m).
  • Binary search finds a value in sorted data by looking at the middle and throwing away the half that cannot contain it. binary_search(b, e, v) only answers yes or no.
  • lower_bound(b, e, v) returns the first position whose value is ≥ v; upper_bound(b, e, v) returns the first position whose value is > v. Both are binary searches.
  • equal_range(b, e, v) returns the pair (lower_bound, upper_bound). Every element between them equals v, so hi − lo is how many times v appears. Example: in 0 1 1 2, equal_range(…, 1) gives positions 1 and 3, so 1 appears 3 − 1 = 2 times.

The full solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> sums(vector<ll> v) {
    vector<ll> s = {0};
    for (ll x : v) {
        int m = s.size();
        for (int i = 0; i < m; i++) s.push_back(s[i] + x);
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll S;
    cin >> n >> S;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    vector<ll> L(a.begin(), a.begin() + n / 2);
    vector<ll> R(a.begin() + n / 2, a.end());
    vector<ll> A = sums(L), Bs = sums(R);
    sort(Bs.begin(), Bs.end());
    ll ans = 0;
    for (ll x : A) {
        auto [lo, hi] = equal_range(Bs.begin(), Bs.end(), S - x);
        ans += hi - lo;
    }
    cout << ans << "\n";
    return 0;
}

auto [lo, hi] = … is a C++17 structured binding: it unpacks the pair returned by equal_range into two iterators.

Input Output Why
4 10 / 2 3 5 7 (sample) 2 the trace above
1 5 / 5 1 n = 1: the left half is empty, its only sum is 0, the right half does all the work
5 100 / 1 2 3 4 5 0 15 is the most you can reach
4 2 / 1 1 1 1 6 any two of the four: C(4, 2) = 6
6 3000000000 / six × 1000000000 20 any three of the six: C(6, 3) = 20
6 9 / 9 1 8 2 7 3 3 {9}, {1, 8}, {2, 7}
40 400 / 1 2 3 … 40 5779890186 in about 0.2 s (it timed out with masks)

Almost six billion subsets of 1 … 40 add up to 400, and we counted them without visiting a single one.

Stress test

The mask brute force against meet in the middle, on 1000 random arrays of up to 12 small offers (values 1 … 10, so many sums repeat):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> sums(vector<ll> v) {
    vector<ll> s = {0};
    for (ll x : v) {
        int m = s.size();
        for (int i = 0; i < m; i++) s.push_back(s[i] + x);
    }
    return s;
}

ll brute(vector<ll> &a, ll S) {
    int n = a.size();
    ll ans = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        ll sum = 0;
        for (int i = 0; i < n; i++) if (mask >> i & 1) sum += a[i];
        ans += (sum == S);
    }
    return ans;
}

ll mitm(vector<ll> &a, ll S) {
    int n = a.size();
    vector<ll> A = sums(vector<ll>(a.begin(), a.begin() + n / 2));
    vector<ll> Bs = sums(vector<ll>(a.begin() + n / 2, a.end()));
    sort(Bs.begin(), Bs.end());
    ll ans = 0;
    for (ll x : A) {
        auto [lo, hi] = equal_range(Bs.begin(), Bs.end(), S - x);
        ans += hi - lo;
    }
    return ans;
}

int main() {
    mt19937 rng(18);
    for (int it = 1; it <= 1000; it++) {
        int n = rng() % 12 + 1;
        vector<ll> a(n);
        for (auto &x : a) x = rng() % 10 + 1;
        ll S = rng() % 30 + 1;
        if (brute(a, S) != mitm(a, S)) {
            cout << "DIFF on test " << it << "\n";
            return 0;
        }
    }
    cout << "OK: 1000 random tests agree\n";
    return 0;
}

Real output: OK: 1000 random tests agree.

(Here 1 << n in an int is safe because n ≤ 12.)

Solutions in C++, Java and Python

C++: the full solution above.

Java (tested on the sample and the edge inputs: 2, 1, 0, 6, 20, 3; on n = 40 it printed 5779890186 in about 0.5 s). Java has no equal_range, so bound is a hand-written lower/upper bound:

import java.io.*;
import java.util.*;

public class Main {
    static long[] sums(long[] v, int from, int to) {
        long[] s = new long[1 << (to - from)];
        int m = 1;
        for (int k = from; k < to; k++) {
            for (int i = 0; i < m; i++) s[m + i] = s[i] + v[k];
            m *= 2;
        }
        return s;
    }

    // first index with b[idx] >= key (strict = false) or b[idx] > key (strict = true)
    static int bound(long[] b, long key, boolean strict) {
        int lo = 0, hi = b.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (b[mid] < key || (strict && b[mid] == key)) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.resetSyntax();
        in.wordChars('0', '9');
        in.wordChars('-', '-');
        in.whitespaceChars(0, ' ');
        in.nextToken(); int n = Integer.parseInt(in.sval);
        in.nextToken(); long S = Long.parseLong(in.sval);
        long[] a = new long[n];
        for (int i = 0; i < n; i++) { in.nextToken(); a[i] = Long.parseLong(in.sval); }
        long[] A = sums(a, 0, n / 2);
        long[] B = sums(a, n / 2, n);
        Arrays.sort(B);
        long ans = 0;
        for (long x : A) ans += bound(B, S - x, true) - bound(B, S - x, false);
        System.out.println(ans);
    }
}

Python (same outputs on the sample and edge inputs; bisect_left / bisect_right are Python's lower_bound / upper_bound). On n = 40 it printed 5779890186 using about 0.5 s of CPU time on our machine (about 1.9 s wall-clock while the machine was busy); with 2^20 sums per half Python is much slower than C++, so on a strict judge with n = 40 it may be close to the time limit:

import sys
from bisect import bisect_left, bisect_right

def sums(v):
    s = [0]
    for x in v:
        s += [y + x for y in s]
    return s

def main():
    data = sys.stdin.read().split()
    n, S = int(data[0]), int(data[1])
    a = list(map(int, data[2:2 + n]))
    A = sums(a[:n // 2])
    B = sorted(sums(a[n // 2:]))
    ans = 0
    for x in A:
        need = S - x
        ans += bisect_right(B, need) - bisect_left(B, need)
    print(ans)

main()

Brute force vs optimal

Brute force (all masks) Meet in the middle
Time O(2^n · n) O(2^(n/2) · n): listing 2 · 2^(n/2) sums, sorting, 2^(n/2) binary searches of ~n/2 steps
Memory O(n) O(2^(n/2)): 2^20 long longs ≈ 8 MB per half
n = 20 ≈ 2·10^7 steps: fine ≈ 2·10^4 steps
n = 40 ≈ 4.4·10^13 steps: TLE ≈ 2·10^7 steps: about 0.2 s
Fits n ≤ ~20 n ≤ ~40

Meet in the middle trades memory for time: the brute force needs almost no memory, while meet in the middle stores two lists of a million sums.

Common mistakes (and the real outputs)

Mistake Input What you see Why Fix
if (binary_search(Bs.begin(), Bs.end(), S - x)) ans++; 4 2 / 1 1 1 1 4 (expected 6) the right sum 1 appears twice, but binary_search only says yes/no, so equal sums are counted once equal_range, ans += hi - lo
vector<int> sums(vector<int> v) (all sums in int) 6 3000000000 / six × 1000000000 18 (expected 20) 3·10^9 inside one half overflows int and wraps to a negative number, so the two sets that use all three of one half never match vector<ll> everywhere
Forgetting sort(Bs.begin(), Bs.end()); 6 9 / 9 1 8 2 7 3 2 (expected 3), no error binary search on unsorted data goes left or right at the wrong moments and misses matches sort the right sums once
Plain masks mask < (1 << n) with n = 40 n = 40 TLE or wrong 2^40 masks; 1 << 40 doesn't even fit in an int split into two halves

The third bug is the nastiest: no crash, no warning, and the sample still prints 2. Only a test like the one above (or a stress test) catches it. The first two bugs also print the correct 2 on the sample, which is why the sample alone proves little.

The bug lines, exactly as in the video (everything else is the full solution):

// Bug 1: replaces the two equal_range lines
        if (binary_search(Bs.begin(), Bs.end(), S - x)) ans++;
// Bug 2: int instead of ll
vector<int> sums(vector<int> v) {
    vector<int> s = {0};
    for (int x : v) {
...
    vector<int> a(n);
...
    vector<int> L(a.begin(), a.begin() + n / 2);
    vector<int> R(a.begin() + n / 2, a.end());
    vector<int> A = sums(L), Bs = sums(R);
...
    for (int x : A) {
// Bug 3: the line sort(Bs.begin(), Bs.end()); is missing
    vector<ll> A = sums(L), Bs = sums(R);
    ll ans = 0;

Mini project

Build a subset-sum toolkit with one sums function and four query modes on the same two half-lists: count = S (equal_range), count ≤ S (upper_bound), the largest sum ≤ S, and XOR instead of +. Add a mask brute force and a random stress test that checks all four modes for n ≤ 12, then time each mode on n = 40.

Practice

  1. Count subsets with sum ≤ S (n ≤ 40).

    Answer Same split. For each left sum <code>x</code>, the partners are right sums <code>≤ S − x</code>; in the sorted right list they are exactly the prefix before <code>upper_bound(Bs.begin(), Bs.end(), S - x)</code>, so add <code>upper_bound(...) - Bs.begin()</code>. For <code>a = 2 3 5 7</code>, <code>S = 10</code> the answer is <code>11</code> (sums 0, 2, 3, 5, 5, 7, 7, 8, 9, 10, 10). Verified against a mask brute force on 2000 random tests.

  2. Largest subset sum that is ≤ S (n ≤ 40).

    Answer For each left sum <code>x ≤ S</code>, the best partner is the largest right sum <code>≤ S − x</code>: the element just before <code>upper_bound(Bs.begin(), Bs.end(), S - x)</code> (it always exists, because 0 is a right sum). Take the maximum of <code>x + partner</code>. For <code>a = 2 3 5 7</code>: <code>S = 11</code> → <code>10</code>, <code>S = 1</code> → <code>0</code> (only the empty set). Verified against a brute force on 2000 random tests.

  3. Count subsets whose XOR is exactly K (n ≤ 40).

    Answer List the XORs of each half (<code>s.push_back(s[i] ^ x)</code>). If the left XOR is <code>x</code>, the right XOR must be <code>y</code> with <code>x ^ y = K</code>, i.e. <code>y = K ^ x</code> (XOR undoes itself). Sort the right list and count <code>K ^ x</code> with <code>equal_range</code>. For <code>a = 1 2 3 4</code>, <code>K = 4</code>: <code>2</code> ({4} and {1, 2, 3, 4}). Verified against a brute force on 2000 random tests.

  4. Largest (subset sum mod M) (n ≤ 35).

    Answer Take every sum mod M, so both lists hold values in <code>[0, M)</code>. For a left value <code>x</code>, <code>x + y</code> is either <code>< M</code> (no wrap) or in <code>[M, 2M)</code> (wraps to <code>x + y − M</code>). Best without wrap: the largest <code>y < M − x</code> (just before <code>lower_bound(..., M - x)</code>; 0 always qualifies). Best with wrap: the largest <code>y</code> overall, giving <code>(x + y) mod M</code>. Take the maximum. For <code>a = 3 5 8</code>, <code>M = 7</code>: <code>6</code>, from {5, 8}: 13 mod 7 = 6 (all three give 16 mod 7 = 2, which is worse). Verified against a brute force on 2000 random tests.

  5. With n = 40, how many sums does each half list, and why is the total far less than 2^40?

    Answer 2^20 = 1,048,576 sums per half, about 2.1·10^6 in total. We never form all pairs; each left sum does one binary search (~20 steps) in the sorted right list, about 2·10^7 steps in all, versus 2^40 · 40 ≈ 4.4·10^13 for the masks.

Quick quiz

a = {1, 2, 3, 4}, S = 5. Left = {1, 2} (sums 0 1 2 3), right = {3, 4} (sums 0 3 4 7). How many subsets have sum exactly 5?

A) 1 · B) 2 · C) 3 · D) 4

Answer

B. Left 0 needs 5: no. Left 1 needs 4: yes ({1, 4}). Left 2 needs 3: yes ({2, 3}). Left 3 needs 2: no. The full solution prints 2 on 4 5 / 1 2 3 4.

Interview questions

  1. What is meet in the middle? Split an exponential search into two halves, enumerate each half separately (2^(n/2) each), and combine them with sorting plus binary search (or hashing) instead of trying every combination.
  2. Why is it much better than "half the work"? Work grows like 2^n, and 2^(n/2) is the square root of 2^n: for n = 40, 10^12 becomes 10^6.
  3. When does it apply? When the answer splits into two independent parts whose results combine by a simple rule (sum equals S, XOR equals K, sum ≤ S), and n is around 30–45.
  4. What is the cost? Memory: O(2^(n/2)) stored values (about 8 MB per half of long longs for n = 40), plus O(2^(n/2) · n) time.
  5. binary_search vs lower_bound vs equal_range? binary_search answers yes/no; lower_bound gives the first element ≥ v; upper_bound the first > v; equal_range gives both, so their difference is the count of v. All need sorted data.
  6. Could you use a hash map instead of sorting? Yes, unordered_map<ll, int> counting right sums works for "exactly S" in expected O(2^(n/2)), but it cannot answer "≤ S" or "largest ≤ S", which need order.

Glossary

Term Meaning Example
Subset Any choice of items, each in or out; order doesn't matter {3, 7} from {2, 3, 5, 7}
Empty subset The choice with no items; its sum is 0 {}
Subset sum The total of the items in a subset {2, 3, 5} → 10
Bitmask (mask) An integer whose bits mark which items are chosen 6 = 0110 → items 1 and 2
1LL << n 2^n as a 64-bit number 1LL << 40
Brute force Try every possibility; slow but surely correct all 2^n masks
Exponential complexity Work like 2^n: each extra item doubles it 2^40 ≈ 1.1·10^12
TLE Time Limit Exceeded: the program was too slow masks on n = 40
Meet in the middle Solve two halves separately, then match their results tunnel dug from both ends
Split Cutting the input into a left half and a right half L = first n/2 items, R = the rest
Independent choices Picking on one side doesn't limit the other side any left part + any right part
Half sums Every subset sum of one half (2^(n/2) values) {2, 3} → 0 2 3 5
Partner / S − x The right sum needed to complete a left sum x x = 3, S = 10 → 7
Sorting Putting values in increasing order 7 0 12 5 → 0 5 7 12
Binary search Finding a value in sorted data by halving the range dictionary lookup, ~20 steps for 10^6
binary_search C++: yes/no, is the value present? true for 7 in 0 5 7 12
lower_bound First position with value ≥ v v = 5 in 0 5 7 12 → index 1
upper_bound First position with value > v v = 5 in 0 5 7 12 → index 2
equal_range The pair (lower_bound, upper_bound); hi − lo = how many times v appears 0 1 1 2, v = 1 → 2
Structured binding C++17 auto [lo, hi] = … unpacks a pair auto [lo, hi] = equal_range(...)
long long (ll) 64-bit integer, up to about 9.2·10^18 sums up to 4·10^10
Integer overflow A value too big for its type wraps around 3·10^9 in an int becomes −1294967296
Stress test Compare a fast solution with a brute force on many random inputs 1000 random arrays
mt19937 C++ random number generator mt19937 rng(18)
Undefined result Output that depends on luck, not logic equal_range on unsorted data
Memory–time trade-off Storing more data to run faster 2 × 8 MB of sums instead of 2^40 steps
XOR (^) Bitwise "exclusive or"; x ^ x = 0 K ^ x in practice 3
Modulo (%) Remainder after division 16 mod 7 = 2

Summary

  • Problem R (Exact Budget): count subsets with sum exactly S, n ≤ 40.
  • Masks are O(2^n · n): correct (2 on the sample) but TLE at n = 40; fine only up to n ≈ 20.
  • Split: every subset = a left part + a right part, chosen independently.
  • List each half's 2^(n/2) sums (start from {0}, each item doubles the list), sort the right ones, and for each left sum x count S − x with equal_range.
  • O(2^(n/2) · n) time, O(2^(n/2)) memory: n = 40 printed 5779890186 in about 0.2 s; 1000 random tests agreed with the brute force.
  • Real bugs: binary_search counts one copy (4, expected 6); int sums overflow (18, expected 20); no sort gives a silent wrong answer (2, expected 3).

Next episode: Number theory 1: divisibility, GCD/LCM, the Euclidean algorithm.