Interactive Programming Education Platform

Logic Practice

Introduction

When faced with a complex problem that involves evaluating multiple options or a large amount of data, relying solely on brute force can be time-consuming. The Meet-in-the-Middle strategy offers a more efficient alternative by dividing the problem, thus simplifying the overall solution process compared to a sequential approach.

Problem Statement:

In this scenario, we need to obtain a group of whole numbers that, when added together, will approach the designated target S without surpassing it.

Examples:

✅ Given: set = {45, 34, 4, 12, 5, 2}, S = 42
✅ Result: 41

The set {34, 5, 2} produces the highest total of 41, which is less than or equal to the value of S.

✅ Given: set = {3, 34, 4, 12, 5, 2}, S = 10
✅ Result: 10

The set {2, 3, 5} adds up to 10, which represents the highest achievable total that is less than or equal to S.

Optimized Approach: Meet-in-the-Middle

When a value of N is chosen to be relatively low yet sufficient for a brute force approach, the Meet-in-the-Middle technique is employed.

This approach divides complex problems into two smaller, manageable parts that can be solved separately. The solutions to these parts are then combined in a straightforward manner.

Steps:

✅ Divide the set of S data into two halves: A (the first N/2 elements) B (the remaining N/2 elements)
✅ Compute all subset sums for both halves: Save all possible sums of A in Array X. Save all possible sums of B in Array Y. Each of these will have at most 2^(N/2) elements instead of 2ⁿ.
✅ Merge the results to find the best subset sum: Sort array Y. For each sum x in X, find the largest y in Y such that x + y ≤ S. Use binary search (O(log 2^(N/2))) instead of brute force (O(2^(N/2))).
✅ A (the first N/2 elements)
✅ B (the remaining N/2 elements)
✅ Save all possible sums of A in Array X.
✅ Save all possible sums of B in Array Y.
✅ Each of these will have at most 2^(N/2) elements instead of 2ⁿ.
✅ Sort array Y.
✅ For each sum x in X, find the largest y in Y such that x + y ≤ S.
✅ Use binary search (O(log 2^(N/2))) instead of brute force (O(2^(N/2))).

Time Complexity Analysis:

✅ Generating all subset sums for A and B: O(2^(N/2))
✅ Sorting Y: O(2^(N/2) log(2^(N/2)))
✅ Searching for the best sum using binary search: O(2^(N/2) log(2^(N/2)))
✅ Final Complexity: O(2^(N/2) * N

Program:

Example


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

using namespace std;
typedef long long ll;

// Function to generate all subset sums for a given range
void computeSubsetSums(const vector<ll>& arr, vector<ll>& subsetSums, int start, int length) {
    int totalSubsets = 1 << length;  // 2^length subsets
    subsetSums.resize(totalSubsets);

    for (int mask = 0; mask < totalSubsets; mask++) {
        ll sum = 0;
        for (int j = 0; j < length; j++) {
            if (mask & (1 << j)) {
                sum += arr[start + j];
            }
        }
        subsetSums[mask] = sum;
    }
}

// Function to find the largest subset sum ≤ target
ll maxSubsetSum(const vector<ll>& arr, ll target) {
    int n = arr.size();
    int mid = n / 2;

    // Compute all subset sums for both halves
    vector<ll> leftSums, rightSums;
    computeSubsetSums(arr, leftSums, 0, mid);
    computeSubsetSums(arr, rightSums, mid, n - mid);

    // Sort rightSums for binary search
    sort(rightSums.begin(), rightSums.end());

    ll maxSum = 0;

    // Check combinations of left and right subset sums
    for (ll leftSum : leftSums) {
        if (leftSum > target) continue;

        // Find the largest rightSum that fits within the target
        auto it = upper_bound(rightSums.begin(), rightSums.end(), target - leftSum);
        if (it != rightSums.begin()) {
            --it; // Move to the largest valid value
            maxSum = max(maxSum, leftSum + *it);
        }
    }

    return maxSum;
}

// Main function
int main() {
    vector<ll> arr = {45, 34, 4, 12, 5, 2};
    ll target = 42;

    cout << "Largest subset sum not exceeding " << target << " is: " 
         << maxSubsetSum(arr, target) << endl;

    return 0;
}

Output:

Output


Largest subset sum not exceeding 42 is: 41

Why Meet-in-the-Middle algorithm is Better?

✅ Brute Force: O(2ⁿ) = 10¹² (Too slow)
✅ Meet-in-the-Middle: O(2ⁿ/² * n) ≈ 10⁶ (Much faster)

This allows for N to be raised as high as 40, making it an ideal option.

Conclusion:

In summary, the Meet-in-the-Middle algorithm proves to be efficient in tackling the subset sums problem as the value of N increases significantly beyond the capabilities of brute force approaches, while still remaining feasible for optimization strategies.

When the issue is divided into smaller segments, computing the necessary upper subset sums, arranging the minor sums, and executing a binary search for the related lower sum produces effective outcomes with minimal complexity.

Meet In The Middle Algorithm In C++