Meet in the Middle

n

vector<long long> get_subsets(int l, int r, const vector<int>& arr) {
    int len = r - l; // [l, r)
    vector<long long> res;

    for (int mask = 0; mask < (1 << len); mask++) {
        long long sum = 0;
        for (int j = 0; j < len; j++) {
            if (mask & (1 << j)) sum += arr[l + j];
        }
        res.push_back(sum);
    }

    return res;
}

// checks if there's a subset in `arr` with sum = S
bool subsetSum(const vector<int>& arr, long long S) {
    int n = (int)arr.size();

    vector<long long> subset1 = get_subsets(0, n / 2, arr);
    vector<long long> subset2 = get_subsets(n / 2, n, arr);

    sort(subset2.begin(), subset2.end());

    for (long long sum : subset1) {
        if (binary_search(subset2.begin(), subset2.end(), S - sum)) {
            return true;
        }
    }
    return false;
}

bool fourSum(const vector<int>& a, int S) {
    int n = (int)a.size();

    // Stores sums of pairs (x, i) where x < i and i is already processed
    unordered_set<int> pairSums;

    for (int i = 0; i < n; i++) {
        // Try pairs (i, j) with j > i
        for (int j = i + 1; j < n; j++) {
            int need = S - (a[i] + a[j]);
            if (pairSums.count(need)) {
                return true;
            }
        }

        // Add all pairs (x, i) for future checks
        for (int x = 0; x < i; x++) {
            pairSums.insert(a[x] + a[i]);
        }
    }

    return false;
}

Introduction to Meet in the Middle

Concept

Subset Sum Problem

Problem Statement

Naive Approach

Meet in the Middle Approach

Implementation

Four-Sum Problem

Problem Statement

Meet in the Middle Approach

Steps

Implementation