Subset Sum Problem | Meet in the Middle

Meet in the Middle (MitM) is an algorithmic technique used to optimize brute-force solutions for problems where the input size is too large for direct approaches. It works by dividing a problem into two smaller subproblems, solving each independently, and then combining their results in an efficient way.

This technique is particularly useful in problems with exponential growth (like subsets or permutations problems), where reducing the problem size by half can significantly improve the performance.

Applications and Use-Cases

Meet in the Middle is commonly used in:

• Subset Sum and Partition Problems where dynamic programming is not feasible due to time or space constraints.
• Problems with moderate input size (typically N ≤ 40) where trying all combinations directly is too slow.
• Problems involving combinations or permutations where it helps to split the solution space into two halves and efficiently combine them.
• Optimization problems like Knapsack variants, finding number of ways to achieve a target sum, or generating constrained subsets.

Understanding Meet in the Middle (MitM)

Meet in the Middle works by:

• Splitting the input into two halves.
• Generate all possible solutions (e.g., subset sums) for each half.
• Use binary search or hash maps to combine the results from both halves efficiently.

This approach brings down the time complexity from O(2^N) to O(2^(N/2) * log(2^(N/2))) or O(2^(N/2) * N/2) for an N-sized problem, in many cases, making it significantly faster for mid-sized input sizes (up to N = 40).

Example Problem

Given an array nums[] of N integers (values can be positive or negative), determine if there exists a non-empty subset whose sum is equal to a given target value.

Constraints

• 1 ≤ N ≤ 40
• -106 <= nums[i] <= 106
• -106 <= target <= 106

Due to N being as large as 40, a brute-force solution checking all 2^N subsets would be too slow.

Sample Input

nums = [3, 4, 8, 2]
target = 10

Sample Output

Subset with target sum exists

Meet in the Middle Approach for Subset Sum

The idea is to split the input array nums into two halves, compute all possible subset sums for each half, and then look for a subset from any half or a pair of sums (one from each half) that together form the target.

This works because splitting the array into two halves gives 2^(N/2) subsets each, which is computationally feasible as compared to O(2^N). The sorted subset sums of one half allow us to use binary search, optimizing the lookup time.

Pseudocode

MEET-IN-THE-MIDDLE-SUBSET-SUM(nums, target):
1.  Split nums[] into two halves: left and right
2.  Generate all subset sums for both halves (leftSums and rightSums)
3.  Sort the subset sums of the left and right half
4.  Return true if target exists in leftSums only OR rightSums only
5.  for each sum in leftSums:
6.      required = target - sum
7.      if required exists in rightSums (using binary search):
8.          return true
9.  return false

Code Implementation

//
//  main.cpp
//  Subset Sum Using Meet in the Middle
//
//
//

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

// Function to generate all possible subset sums
void generateSubsetSums(const vector<int>& nums, vector<int>& subsetSums) {
    int n = (int) nums.size();
    int totalSubsets = 1 << n; // 2^n subsets

    for (int mask = 1; mask < totalSubsets; mask++) {
        int sum = 0;
        for (int j = 0; j < n; j++) {
            if (mask & (1 << j)) { // If j-th element is in the subset
                sum += nums[j];
            }
        }
        
        subsetSums.push_back(sum);
    }
}

bool meetInTheMiddleSubsetSum(vector<int>& nums, int target) {
    int n = (int) nums.size();
    int mid = n / 2;

    // Divide the array into two halves
    vector<int> left(nums.begin(), nums.begin() + mid);
    vector<int> right(nums.begin() + mid, nums.end());

    // Generate all subset sums for both halves
    vector<int> leftSums, rightSums;
    generateSubsetSums(left, leftSums);
    generateSubsetSums(right, rightSums);

    // Sort leftSums and rightSums to use binary search
    sort(leftSums.begin(), leftSums.end());
    sort(rightSums.begin(), rightSums.end());
    
    // Check if a subset sum from left half only or right half only equals target
    if (binary_search(leftSums.begin(), leftSums.end(), target) ||
        binary_search(rightSums.begin(), rightSums.end(), target)) {
        return true;
    }

    // Check if any subset sum from leftSums matches with rightSums to form target
    for (int sum : leftSums) {
        int required = target - sum;
        if (binary_search(rightSums.begin(), rightSums.end(), required)) {
            return true;
        }
    }
    
    return false;
}

int main() {
    vector<int> nums = {3, 4, 8, 2};
    int target = 10;

    if (meetInTheMiddleSubsetSum(nums, target)) {
        cout << "Subset with target sum exists" << endl;
    } else {
        cout << "No subset with target sum found" << endl;
    }

    return 0;
}

Output

Subset with target sum exists

Time Complexity

• Generating subset sums: O(2^(N/2) * N/2)
• Sorting and binary search: O(2^(N/2) * log(2^(N/2)))
• Overall time complexity: O(2^(N/2) * log(2^(N/2))) or O(2^(N/2) * N/2), which is much faster than O(2^N)

Space Complexity

O(2^(N/2)) – due to two arrays used to store subset sums

This method helps solve problems efficiently when N is around 30-40, where brute-force is infeasible.