AntInLoop

Problem Decomposition & Reductions

Problem Decomposition breaks complex algorithmic challenges into independent, solvable subproblems—such as Meet-in-the-Middle, prefix/suffix splitting, and graph condensation—to slash time complexity.

Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code

Problem Decomposition & Reductions

Problem Decomposition breaks a seemingly intractable problem into simpler, independent pieces whose answers combine cleanly:

1. Prefix / Suffix Split: Precompute left-to-right and right-to-left summaries (e.g., Product Except Self, Longest Bitonic Subsequence).

2. Meet-in-the-Middle: Split an $n = 40$ exponential problem ($O(2^{40})$ TLE!) into two halves of size 20 ($2 \times 2^{20} \approx 2 \times 10^6$ — instant!) and merge with binary search or two pointers!

3. Condensation / Component Split: Collapse cycles into SCCs via Tarjan/Kosaraju to reduce any directed graph to a DAG.

---

Classic Example: Meet-in-the-Middle Subset Sum ($n \le 40$)

Count subsets of a (size $n \le 40$) summing to target in $O(n \cdot 2^{n/2})$ instead of $O(2^n)$!

<details>

<summary>Show C++ Solution</summary>

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

std::vector<long long> allSubsetSums(const std::vector<int>& a, int l, int r) {
    std::vector<long long> sums = {0};
    for (int i = l; i < r; ++i) {
        size_t sz = sums.size();
        for (size_t j = 0; j < sz; ++j) sums.push_back(sums[j] + a[i]);
    }
    return sums;
}

long long countSubsetsMITM(const std::vector<int>& a, long long target) {
    int n = static_cast<int>(a.size()), mid = n / 2;
    auto left = allSubsetSums(a, 0, mid);
    auto right = allSubsetSums(a, mid, n);
    std::sort(right.begin(), right.end());

    long long count = 0;
    for (long long s : left) {
        auto [lo, hi] = std::equal_range(right.begin(), right.end(), target - s);
        count += (hi - lo);
    }
    return count;
}

int main() {
    std::cout << countSubsetsMITM({1, 2, 3, 4, 5}, 5) << "\n"; // {5}, {2,3}, {1,4} -> 3
    return 0;
}

</details>

---

Related Topics