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>
---