Meet-in-the-Middle¶
Meet-in-the-middle is an optimization technique that splits the search space in half, solves each half independently, and then combines the results. This approach can reduce exponential time complexity from O(2^n) to O(2^(n/2)), making it feasible to solve problems that would otherwise be intractable.
How It Works¶
- Split: Divide the problem into two equal or nearly equal parts
- Solve Independently: Solve each part separately using brute force
- Combine: Merge the results from both parts to find the final solution
Basic Template¶
#include <vector>
#include <algorithm>
using namespace std;
// Sketch: split into halves, brute-force each half, merge (see examples below).
Example: Subset Sum Problem¶
Problem: Find if there exists a subset that sums to a target value using meet-in-the-middle.
Sample Input:
- arr = [1, 2, 3, 4, 5, 6]
- target = 9
Sample Output: true (subsets like [1,2,6], [3,6], [4,5] sum to 9)
#include <vector>
#include <algorithm>
using namespace std;
vector<int> generateSubsetSums(const vector<int>& arr, int start, int end) {
vector<int> sums;
int n = end - start;
for (int mask = 0; mask < (1 << n); mask++) {
int sum = 0;
for (int i = 0; i < n; i++)
if (mask & (1 << i)) sum += arr[start + i];
sums.push_back(sum);
}
sort(sums.begin(), sums.end());
return sums;
}
bool subsetSumMeetInMiddle(vector<int>& arr, int target) {
int n = (int)arr.size(), mid = n / 2;
vector<int> leftSums = generateSubsetSums(arr, 0, mid);
vector<int> rightSums = generateSubsetSums(arr, mid, n);
for (int leftSum : leftSums) {
if (leftSum == target) return true;
if (binary_search(rightSums.begin(), rightSums.end(), target - leftSum))
return true;
}
return false;
}
Example: 4-Sum Problem¶
Problem: Find all unique quadruplets that sum to a target value.
Sample Input:
- nums = [1, 0, -1, 0, -2, 2]
- target = 0
Sample Output:
#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>
using namespace std;
vector<vector<int>> fourSumMeetInMiddle(vector<int>& nums, int target) {
int n = (int)nums.size();
if (n < 4) return {};
sort(nums.begin(), nums.end());
set<vector<int>> result;
int mid = n / 2;
unordered_map<int, vector<pair<int, int>>> leftPairs;
for (int i = 0; i < mid; i++)
for (int j = i + 1; j < mid; j++)
leftPairs[nums[i] + nums[j]].push_back({i, j});
unordered_map<int, vector<pair<int, int>>> rightPairs;
for (int i = mid; i < n; i++)
for (int j = i + 1; j < n; j++)
rightPairs[nums[i] + nums[j]].push_back({i, j});
for (auto& lp : leftPairs) {
int need = target - lp.first;
if (rightPairs.find(need) == rightPairs.end()) continue;
for (auto& left : lp.second)
for (auto& right : rightPairs[need]) {
vector<int> q = {nums[left.first], nums[left.second],
nums[right.first], nums[right.second]};
sort(q.begin(), q.end());
result.insert(q);
}
}
return vector<vector<int>>(result.begin(), result.end());
}
Advanced Applications¶
Closest Subset Sum¶
#include <vector>
#include <algorithm>
#include <climits>
#include <cstdlib>
using namespace std;
vector<int> subsetSumsUnsorted(const vector<int>& arr, int start, int end) {
vector<int> sums;
int n = end - start;
for (int mask = 0; mask < (1 << n); mask++) {
int sum = 0;
for (int i = 0; i < n; i++)
if (mask & (1 << i)) sum += arr[start + i];
sums.push_back(sum);
}
return sums;
}
int closestSubsetSum(vector<int>& arr, int target) {
int n = (int)arr.size(), mid = n / 2;
vector<int> leftSums = subsetSumsUnsorted(arr, 0, mid);
vector<int> rightSums = subsetSumsUnsorted(arr, mid, n);
sort(leftSums.begin(), leftSums.end());
sort(rightSums.begin(), rightSums.end());
int closest = INT_MAX;
for (int leftSum : leftSums) {
int need = target - leftSum;
auto it = lower_bound(rightSums.begin(), rightSums.end(), need);
if (it != rightSums.end())
closest = min(closest, abs(target - (leftSum + *it)));
if (it != rightSums.begin())
closest = min(closest, abs(target - (leftSum + *(it - 1))));
}
return closest;
}
Maximum XOR Subset¶
#include <vector>
#include <algorithm>
using namespace std;
vector<int> generateSubsetXors(const vector<int>& arr, int start, int end) {
vector<int> xors;
int n = end - start;
for (int mask = 0; mask < (1 << n); mask++) {
int x = 0;
for (int i = 0; i < n; i++)
if (mask & (1 << i)) x ^= arr[start + i];
xors.push_back(x);
}
return xors;
}
int maxXorSubsetMeetInMiddle(vector<int>& arr) {
int n = (int)arr.size(), mid = n / 2;
vector<int> left = generateSubsetXors(arr, 0, mid);
vector<int> right = generateSubsetXors(arr, mid, n);
int best = 0;
for (int a : left)
for (int b : right) best = max(best, a ^ b);
return best;
}
Use Cases¶
Optimization Problems¶
- Subset Sum: Finding subsets that sum to a target
- Knapsack Variants: When the problem can be split into two parts
- Partition Problems: Dividing sets into two equal parts
- Closest Pair: Finding closest elements in high dimensions
Search Problems¶
- 4-Sum and Higher: Finding k-tuples that sum to target
- Maximum XOR: Finding maximum XOR of subsets
- Palindrome Partitioning: When the problem has symmetric structure
- Graph Problems: Finding paths or cycles in large graphs
Mathematical Problems¶
- Integer Factorization: When the factors can be split
- Discrete Logarithm: Cryptographic applications
- Lattice Problems: Finding shortest vectors
- Combinatorial Optimization: When the search space can be halved
Complexity Analysis¶
Time Complexity¶
- Standard Brute Force: O(2^n)
- Meet-in-the-Middle: O(2^(n/2) × log(2^(n/2))) = O(2^(n/2) × n)
- Space Complexity: O(2^(n/2)) for storing intermediate results
When to Use Meet-in-the-Middle¶
- Problem can be naturally split into two independent parts
- Each part can be solved independently
- Results can be efficiently combined
- Standard brute force would be too slow (n > 20-25)
Optimization Tips¶
- Choose Split Point: Optimize where to split the problem
- Sort Results: Sort one half for efficient binary search
- Use Hash Maps: For O(1) lookup when combining results
- Prune Early: Eliminate impossible combinations early
- Memory Management: Be careful with memory usage for large halves
- Parallel Processing: Each half can be solved in parallel