Meet in the Middle

Banyak soal memiliki kompleksitas eksponensial — contoh klasik: subset sum dengan n = 40 membutuhkan O(2⁴⁰) ≈ 10¹² operasi, jelas TLE. Meet in the middle membagi masalah menjadi dua bagian sama besar, selesaikan masing-masing O(2^(n/2)), lalu gabungkan. Hasilnya: O(2^(n/2) · n/2). Untuk n = 40, ini menjadi sekitar 10⁶ — sangat layak. Pada Chapter ini kita akan mempelajari teknik ini dengan satu contoh utama: subset sum n=40, dan satu varian singkat: 4-sum.

Intuisi: Bagi Dua, Lalu Gabung #

Aturan #

Untuk soal dengan kompleksitas O(2^n) atau O(n^k) dengan k besar, bila kita bisa membagi input menjadi dua bagian independen, kompleksitas dapat dipangkas ke O(2^(n/2)) atau O(n^(k/2)).

Mekanisme #

Bagi input menjadi left = a[0..n/2-1] dan right = a[n/2..n-1].
Bangun daftar semua kemungkinan sub-masalah untuk left dan right secara terpisah.
Urutkan salah satu daftar (biasanya right).
Untuk setiap elemen di daftar lainnya, gunakan binary search pada daftar yang terurut untuk menemukan pasangan yang memenuhi kondisi.

flowchart LR A["n=40, target=T"] --> B["left=a[0..19], right=a[20..39]"] B --> C["subsets_left: 2^20 subset sums"] B --> D["subsets_right: 2^20 subset sums"] C --> E["Sort subsets_right"] E --> F["For each s_left, binary search T-s_left in subsets_right"] D --> E

Aplikasi: Subset Sum n=40 #

Aturan #

Diberikan array a berukuran n (n ≤ 40) dan target T, tentukan apakah ada subset dengan jumlah tepat T. Solusi brute force: O(2^n) — tidak layak. Meet in the middle: O(2^(n/2) · n/2).

Mekanisme #

Bagi a jadi left = a[0..mid-1] dan right = a[mid..n-1].
Enumerasi semua subset sum dari left → sl (maks 2^20 elemen).
Enumerasi semua subset sum dari right → sr (maks 2^20 elemen).
Sort sr.
Untuk setiap x di sl, cek apakah T - x ada di sr via binary search. Bila ya, jawab true.

Kode: Subset Sum via Meet in the Middle #

cpp
#include <iostream>
#include <vector>
#include <algorithm>

void gen_subsets(const std::vector<long long>& a, std::vector<long long>& out) {
    int n = static_cast<int>(a.size());
    out.reserve(1LL << n);
    for (int mask = 0; mask < (1 << n); ++mask) {
        long long sum = 0;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) sum += a[i];
        }
        out.push_back(sum);
    }
}

bool subset_sum(const std::vector<long long>& a, long long T) {
    int n = static_cast<int>(a.size());
    int mid = n / 2;
    std::vector<long long> left(a.begin(), a.begin() + mid);
    std::vector<long long> right(a.begin() + mid, a.end());

    std::vector<long long> sl, sr;
    gen_subsets(left, sl);
    gen_subsets(right, sr);

    std::sort(sr.begin(), sr.end());

    for (long long x : sl) {
        long long need = T - x;
        auto it = std::lower_bound(sr.begin(), sr.end(), need);
        if (it != sr.end() && *it == need) return true;
    }
    return false;
}

int main() {
    std::vector<long long> a = {
        1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683,
        59049, 177147, 531441, 1594323, 4782969, 14348907,
        43046721, 129140163, 387420489, 1162261467LL,
        2, 6, 18, 54, 162, 486, 1458, 4374, 13122, 39366,
        118098, 354294, 1062882, 3188646, 9565938, 28697814LL,
        86093442LL, 258280326LL, 774840978LL, 2324522934LL
    };
    std::cout << "n = " << a.size() << '\n';
    for (long long t : {100LL, 30LL, 1LL, 1000000000LL, 100000000000LL}) {
        std::cout << "target " << t << ": "
                  << (subset_sum(a, t) ? "ADA" : "TIDAK") << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
n = 40
target 100: ADA
target 30: ADA
target 1: ADA
target 1000000000: ADA
target 100000000000: TIDAK

Fungsi gen_subsets: enumerasi semua 2^|a| subset sum. Untuk |a| = 20, ini 2²⁰ ≈ 10⁶ elemen — layak.
Baris int mid = n / 2;: bagi array di tengah. Untuk n = 40, mid = 20.
Baris std::vector<long long> left(a.begin(), a.begin() + mid);: potong bagian kiri.
Baris std::sort(sr.begin(), sr.end());: sort daftar subset sum kanan agar bisa binary search. O(2^m log 2^m) = O(m · 2^m).
Baris for (long long x : sl): iterasi setiap subset sum dari kiri. O(2^m).
Baris auto it = std::lower_bound(sr.begin(), sr.end(), need);: binary search T - x di sr. O(log 2^m) = O(m).
Baris if (it != sr.end() && *it == need) return true;: bila ketemu, jawab true. Bila lower_bound mengembalikan elemen lain (*it != need), tidak ada subset cocok untuk x ini.
Hasil target 100: ADA: subset {1, 18, 27, 54} = 100 (atau kombinasi lain).
Hasil target 30: ADA: subset {1, 2, 27} = 30.
Hasil target 100000000000: TIDAK: target 100 milyar melebihi total array (~5,2 milyar), tidak mungkin tercapai.

Varian: 4-Sum #

Aturan #

Diberikan array a berukuran n (n ≤ 200), cari empat indeks berbeda i, j, k, l dengan a[i] + a[j] + a[k] + a[l] = T. Solusi brute force O(n⁴). Meet in the middle: O(n² log n).

Mekanisme #

Enumerasi semua pasangan (i, j) dengan i < j → simpan (a[i] + a[j], i, j). Sort berdasarkan jumlah. Untuk setiap pasangan, binary search T - jumlah. Verifikasi indeks berbeda.

Ringkasan #

Meet in the middle memangkas O(2^n) → O(2^(n/2) · n/2) dengan membagi input menjadi dua bagian independen.
Subset sum n=40: enumerasi subset sum kiri + kanan (masing-masing 2^20), sort salah satu, binary search. Total ~10⁶ operasi.
4-sum: enumerasi pasangan (i,j) → O(n²), sort, binary search. Total O(n² log n).
Perhatikan batas memori — setiap bagian menyimpan 2^(n/2) elemen, jadi long long × 2^25 ≈ 256 MB untuk n = 50.