Meet in the Middle

Wiki › Thuật toán

huunguyen · Last updated 8, Tháng 4, 2026, 21:43

Meet in the Middle (gặp nhau ở giữa) là kỹ thuật chia bài toán thành hai nửa, giải mỗi nửa độc lập, rồi kết hợp kết quả — giảm từ $O (2^{N})$ xuống $O (2^{N / 2} \cdot \log)$ .

Ứng dụng: Các bài toán subset/brute force với $N \leq 40$ (thay vì $N \leq 20$ cho brute force thông thường).

Bài toán điển hình: Subset Sum

Cho mảng $n$ số, đếm số subset có tổng $= K$ . Với $n \leq 40$ , brute force $O (2^{40})$ quá chậm.

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

long long count_subsets(vector<long long>& a, long long K) {
    int n = a.size();
    int half = n / 2;

    // Sinh tất cả tổng của nửa trái
    vector<long long> left_sums;
    for (int mask = 0; mask < (1 << half); mask++) {
        long long s = 0;
        for (int i = 0; i < half; i++)
            if (mask >> i & 1) s += a[i];
        left_sums.push_back(s);
    }

    // Sinh tất cả tổng của nửa phải
    vector<long long> right_sums;
    for (int mask = 0; mask < (1 << (n - half)); mask++) {
        long long s = 0;
        for (int i = 0; i < n - half; i++)
            if (mask >> i & 1) s += a[half + i];
        right_sums.push_back(s);
    }

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

    long long cnt = 0;
    for (long long ls : left_sums) {
        long long need = K - ls;
        cnt += upper_bound(right_sums.begin(), right_sums.end(), need)
             - lower_bound(right_sums.begin(), right_sums.end(), need);
    }
    return cnt;
}

Độ phức tạp: $O (2^{N / 2} \cdot N / 2)$ sinh + $O (2^{N / 2} \log)$ tìm kiếm = $O (2^{N / 2} \cdot N)$ .

Bài toán: Closest Subset Sum

Tìm subset có tổng gần $K$ nhất:

long long closest_subset_sum(vector<long long>& a, long long K) {
    int n = a.size(), half = n / 2;

    auto gen = [&](int from, int to) {
        vector<long long> sums;
        for (int mask = 0; mask < (1 << (to - from)); mask++) {
            long long s = 0;
            for (int i = from; i < to; i++)
                if (mask >> (i - from) & 1) s += a[i];
            sums.push_back(s);
        }
        return sums;
    };

    auto L = gen(0, half);
    auto R = gen(half, n);
    sort(R.begin(), R.end());

    long long ans = LLONG_MAX;
    for (long long ls : L) {
        long long need = K - ls;
        auto it = lower_bound(R.begin(), R.end(), need);
        if (it != R.end())
            ans = min(ans, abs(ls + *it - K));
        if (it != R.begin())
            ans = min(ans, abs(ls + *prev(it) - K));
    }
    return ans;   // giá trị |sum - K| nhỏ nhất
}

Bài toán: 4-Sum

Tìm 4 phần tử trong mảng có tổng $= K$ trong $O (N^{2} \log N)$ :

bool four_sum(vector<int>& a, int K) {
    int n = a.size();
    // Sinh tất cả tổng đôi
    vector<pair<int,int>> pairs;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            pairs.push_back({a[i]+a[j], i*n+j});

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

    for (auto& [s, idx] : pairs) {
        int need = K - s;
        auto it = lower_bound(pairs.begin(), pairs.end(), make_pair(need, 0));
        while (it != pairs.end() && it->first == need) {
            // Kiểm tra 4 chỉ số phân biệt
            int i1 = idx/n, j1 = idx%n;
            int i2 = it->second/n, j2 = it->second%n;
            if (i1!=i2 && i1!=j2 && j1!=i2 && j1!=j2) return true;
            ++it;
        }
    }
    return false;
}

Ứng dụng khác

Knapsack với $n \leq 40$ : Sinh tất cả trạng thái nửa trái/phải, merge.
Game states: Brute force trạng thái từ hai phía rồi gặp nhau.
Cryptography: Birthday attack dùng MITM.

Khi nào dùng Meet in the Middle?

	Brute Force	Meet in the Middle
Giới hạn $N$	$\leq 20$	$\leq 40$
Độ phức tạp	$O (2^{N})$	$O (2^{N / 2} \log)$
Bộ nhớ	$O (1)$	$O (2^{N / 2})$

Dùng khi bài có dạng "liệt kê tất cả subset/combination" nhưng $N$ quá lớn cho $O (2^{N})$ .

Bài tập minh họa

Hoàng Tử Lai (halfblood) — Subset sum / kết hợp hai nửa.

Bình luận

Không có bình luận tại thời điểm này.