Meet in the Middle — Kỹ thuật chia để trị nâng cao

Khi brute force đòi hỏi O(2ⁿ) — quá chậm cho n=40 nhưng lại đủ nhanh cho n=20 — Meet in the Middle là vũ khí bí mật. Thay vì duyệt toàn bộ 2⁴⁰ ≈ 10¹² tổ hợp, ta chia đôi bài toán thành hai nửa 2²⁰ ≈ 10⁶, giải từng nửa rồi ghép kết quả ở giữa.

🎯 Mục tiêu

Sau bài này, bạn sẽ:

• Hiểu ý tưởng cốt lõi: chia đôi → brute force mỗi nửa → ghép thông minh
• Giảm O(2ⁿ) xuống O(2^(n/2) × log(2^(n/2))) = O(n × 2^(n/2))
• Áp dụng cho Subset Sum, Closest Sum, và Bidirectional BFS
• Nhận biết khi nào Meet in the Middle là lựa chọn tối ưu

Bức tranh tư duy — Tại sao chia đôi hiệu quả?

Hình dung bạn cần tìm hai người trong đám đông 1 triệu người mà tổng chiều cao bằng đúng 3.5m. Cách brute force: thử mọi cặp → C(10⁶, 2) ≈ 5 × 10¹¹ cặp.

Cách Meet in the Middle: chia đám đông thành hai nhóm 500.000 người. Đo chiều cao từng nhóm, sắp xếp một nhóm, rồi với mỗi người ở nhóm kia, dùng binary search tìm người bù → chỉ cần ~500.000 × log(500.000) ≈ 10⁷ thao tác.

Brute Force:   O(2^40) = 1,099,511,627,776  ← KHÔNG KHẢ THI

Meet in Middle: O(2^20 × 20) ≈ 20,971,520   ← RẤT NHANH
                    ↑           ↑
               Brute mỗi nửa  Binary search ghép

💡 HPN's Insight

Meet in the Middle không phải Divide & Conquer truyền thống. Trong D&C, bài con có cùng cấu trúc với bài gốc. Còn MitM, mỗi nửa chỉ là nửa input — ta brute force mỗi nửa rồi dùng kỹ thuật ghép (sorting + binary search hoặc hash map) để tìm đáp án.

Thuật toán — Bước từng bước

Bước 1: Chia đôi input

Chia mảng/tập hợp kích thước n thành hai nửa: A[0..n/2-1] và B[n/2..n-1].

Bước 2: Brute force mỗi nửa

Liệt kê tất cả tổ hợp có thể của mỗi nửa:

• Nửa A → tạo tập SA chứa 2^(n/2) giá trị
• Nửa B → tạo tập SB chứa 2^(n/2) giá trị

Bước 3: Ghép kết quả

Sắp xếp một tập (ví dụ SB), rồi với mỗi phần tử a ∈ SA, dùng binary search tìm b ∈ SB sao cho a + b thỏa điều kiện.

Input:  [a₁, a₂, ..., aₙ]
         ├──────┤├──────┤
         Nửa A    Nửa B

Step 1:  SA = tất cả subset sums của nửa A  (2^(n/2) giá trị)
Step 2:  SB = tất cả subset sums của nửa B  (2^(n/2) giá trị)
Step 3:  Sort(SB)
Step 4:  Với mỗi a ∈ SA: binary_search(SB, target - a)

Bài toán kinh điển

1. Subset Sum — Tìm tập con có tổng bằng target

Đề bài: Cho mảng n phần tử, kiểm tra có tập con nào có tổng đúng bằng target không?

Python

from itertools import combinations
from bisect import bisect_left

def meet_in_middle_subset_sum(arr, target):
    n = len(arr)
    mid = n // 2
    left, right = arr[:mid], arr[mid:]

    def all_subset_sums(part):
        """Liệt kê tổng của mọi tập con."""
        sums = []
        for size in range(len(part) + 1):
            for combo in combinations(part, size):
                sums.append(sum(combo))
        return sums

    # Brute force mỗi nửa
    left_sums = all_subset_sums(left)
    right_sums = sorted(all_subset_sums(right))

    # Ghép: tìm a + b == target
    for a in left_sums:
        b = target - a
        idx = bisect_left(right_sums, b)
        if idx < len(right_sums) and right_sums[idx] == b:
            return True
    return False

# Test
arr = [3, 7, 1, 8, -5, 2, 14, 9, 6, -3]
print(meet_in_middle_subset_sum(arr, 25))  # True

C++

#include <vector>
#include <algorithm>

bool meetInMiddleSubsetSum(std::vector<int>& arr, int target) {
    int n = arr.size();
    int mid = n / 2;

    auto allSubsetSums = [](std::vector<int>& part) {
        int m = part.size();
        std::vector<long long> sums;
        for (int mask = 0; mask < (1 << m); ++mask) {
            long long s = 0;
            for (int i = 0; i < m; ++i)
                if (mask & (1 << i)) s += part[i];
            sums.push_back(s);
        }
        return sums;
    };

    std::vector<int> left(arr.begin(), arr.begin() + mid);
    std::vector<int> right(arr.begin() + mid, arr.end());

    auto leftSums = allSubsetSums(left);
    auto rightSums = allSubsetSums(right);
    std::sort(rightSums.begin(), rightSums.end());

    for (long long a : leftSums) {
        long long b = target - a;
        if (std::binary_search(rightSums.begin(), rightSums.end(), b))
            return true;
    }
    return false;
}

2. Closest Sum — Tổng tập con gần target nhất

Đề bài: Tìm tập con có tổng gần target nhất (minimize |sum - target|).

from bisect import bisect_left

def closest_subset_sum(arr, target):
    n = len(arr)
    mid = n // 2
    left, right = arr[:mid], arr[mid:]

    def all_subset_sums(part):
        sums = [0]
        for x in part:
            sums += [s + x for s in sums]
        return sums

    left_sums = all_subset_sums(left)
    right_sums = sorted(all_subset_sums(right))
    best = float('inf')

    for a in left_sums:
        remain = target - a
        idx = bisect_left(right_sums, remain)
        # Kiểm tra idx và idx-1 (nearest neighbors)
        for j in [idx - 1, idx]:
            if 0 <= j < len(right_sums):
                total = a + right_sums[j]
                best = min(best, abs(total - target))

    return best

arr = [3, 7, 1, 8, 5, 2]
print(closest_subset_sum(arr, 15))  # 0 (subset {7, 8} = 15)

3. Bidirectional BFS — Tìm đường ngắn nhất

Bidirectional BFS là ứng dụng Meet in the Middle cho tìm đường trong đồ thị:

BFS thường:  Mở rộng từ source → O(b^d)
             b = branching factor, d = khoảng cách

Bidirectional: Mở rộng từ CẢ source VÀ target
               Gặp nhau ở giữa → O(b^(d/2)) + O(b^(d/2)) = O(2 × b^(d/2))

from collections import deque

def bidirectional_bfs(graph, source, target):
    if source == target:
        return 0

    front_visited = {source: 0}
    back_visited = {target: 0}
    front_queue = deque([source])
    back_queue = deque([target])

    while front_queue and back_queue:
        # Mở rộng phía có ít node hơn
        if len(front_queue) <= len(back_queue):
            result = _expand(graph, front_queue, front_visited, back_visited)
        else:
            result = _expand(graph, back_queue, back_visited, front_visited)
        if result is not None:
            return result

    return -1  # Không tìm thấy đường

def _expand(graph, queue, visited, other_visited):
    node = queue.popleft()
    for neighbor in graph.get(node, []):
        if neighbor not in visited:
            visited[neighbor] = visited[node] + 1
            queue.append(neighbor)
        if neighbor in other_visited:
            return visited[neighbor] + other_visited[neighbor]
    return None

Phân tích độ phức tạp

Kỹ thuật	Time	Space	Áp dụng khi
Brute Force	O(2ⁿ)	O(1)	n ≤ 20
Meet in the Middle	O(2^(n/2) × n)	O(2^(n/2))	20 < n ≤ 40
DP (nếu áp dụng được)	O(n × target)	O(target)	target nhỏ
Bidirectional BFS	O(b^(d/2))	O(b^(d/2))	Đồ thị lớn

⚠️ Giới hạn của Meet in the Middle

• Chỉ hiệu quả khi n ≈ 30-40. Với n > 50, ngay cả 2^(n/2) cũng quá lớn
• Cần O(2^(n/2)) bộ nhớ — có thể lớn (2^20 ≈ 10⁶ phần tử, OK; 2^25 ≈ 3.3×10⁷, cần cẩn thận)
• Không phải lúc nào cũng bài toán chia được thành hai nửa độc lập

⚠️ Cạm bẫy

Sai lầm điển hình khi dùng Meet in the Middle:

1. Chia không đều — Luôn chia thành hai nửa gần bằng nhau. Nếu chia 10-30 thay vì 20-20, nửa lớn 2³⁰ ≈ 10⁹ vẫn quá chậm

2. Quên sắp xếp trước khi binary search — Sau khi brute force nửa B, phải sort tập SB trước khi binary search. Quên sort → tìm kiếm sai hoặc O(n) thay vì O(log n)

3. Tràn số (overflow) — Tổng subset có thể rất lớn. Dùng long long trong C++ hoặc chú ý overflow trong Python khi so sánh

4. Dùng MitM khi DP tốt hơn — Nếu target nhỏ (< 10⁶), DP knapsack O(n × target) thường nhanh hơn MitM. Chỉ dùng MitM khi target quá lớn cho DP

5. Không xử lý duplicate — Nửa trái và nửa phải có thể tạo ra nhiều tổng trùng nhau. Dùng set hoặc unique() để tránh công thừa

Nhận biết bài toán Meet in the Middle

Dấu hiệu nhận biết:

• Input size n ≈ 30-40 (quá lớn cho 2ⁿ, quá nhỏ cho DP)
• Bài toán liên quan đến tập con, tổ hợp, hoặc đường đi
• Có thể chia input thành hai nửa độc lập
• Kết quả cuối cùng là tổng/ghép từ hai nửa

Decision Tree:
┌─ n ≤ 20? → Brute Force O(2ⁿ) ✅
├─ 20 < n ≤ 40 & chia đôi được? → Meet in the Middle ✅
├─ Target nhỏ & có optimal substructure? → DP ✅
└─ n > 50 & không DP được? → Heuristics / Approximation

🧠 Quiz

Câu 1: Meet in the Middle giảm độ phức tạp từ O(2ⁿ) xuống bao nhiêu?

• [ ] A) O(n²)
• [ ] B) O(n log n)
• [x] C) O(2^(n/2) × n)
• [ ] D) O(n × 2ⁿ)

💡 Giải thích: Ta chia input thành 2 nửa kích thước n/2. Brute force mỗi nửa O(2^(n/2)), sắp xếp một nửa O(2^(n/2) × n/2), rồi binary search ghép O(2^(n/2) × log(2^(n/2))) = O(2^(n/2) × n/2). Tổng ≈ O(2^(n/2) × n). So với O(2⁴⁰) ≈ 10¹², O(2²⁰ × 40) ≈ 4×10⁷ — nhanh hơn ~25.000 lần!

Câu 2: Khi nào KHÔNG nên dùng Meet in the Middle?

• [ ] A) Khi n = 36 và cần tìm subset sum
• [x] B) Khi n = 100 và target = 1000 (DP knapsack phù hợp hơn)
• [ ] C) Khi cần tìm đường ngắn nhất trong đồ thị có branching factor lớn
• [ ] D) Khi n = 40 và brute force O(2⁴⁰) quá chậm

💡 Giải thích: Với n = 100, 2^(n/2) = 2⁵⁰ ≈ 10¹⁵ — MitM vẫn quá chậm. Nhưng target = 1000 → DP knapsack chạy O(100 × 1000) = 10⁵, rất nhanh. MitM chỉ phù hợp khi n ≈ 30-40 VÀ target quá lớn cho DP.

Câu 3: Trong Bidirectional BFS, tại sao nên mở rộng phía có ít node hơn trước?

• [ ] A) Để đảm bảo tìm đường ngắn nhất
• [ ] B) Để giảm bộ nhớ sử dụng
• [x] C) Để giữ hai mặt trận BFS cân bằng, tối ưu tổng số node duyệt
• [ ] D) Vì phía có ít node luôn gần target hơn

💡 Giải thích: BFS mở rộng theo lớp — mỗi lớp lớn hơn lớp trước (theo branching factor b). Nếu luôn mở rộng phía nhỏ hơn, ta giữ cả hai phía ở kích thước tương đương → tổng node duyệt ≈ 2 × b^(d/2) thay vì b^d. Đây là heuristic cân bằng.

📚 Bài liên quan

Bài liên quan trong Penalgo

• → Sliding Window — Kỹ thuật tối ưu khác: giảm O(n²) xuống O(n) cho bài toán dãy con liên tiếp
• → Binary Search — Nền tảng của bước ghép trong MitM
• → Bitmask DP — Khi n ≤ 20, bitmask DP là lựa chọn thay thế cho brute force
• → BFS & DFS — Nền tảng để hiểu Bidirectional BFS
• ← Tổng quan Optimization Patterns — Roadmap các kỹ thuật tối ưu

Từ khóa glossary: Meet in the Middle, Subset Sum, Closest Sum, Bidirectional BFS, exponential optimization, divide and conquer