Meet-in-the-Middle Algorithm in C++

24 May 2025 | 3 min read

Introduction

When looking for a solution to a problem that requires tackling numerous options or a considerable volume of data, a brute force method can take far too long. The Meet-in-the-Middle approach is an efficient way to split a problem, which makes it simpler than attempting to solve everything sequentially.

Problem Statement:

In this problem, we are required to retrieve a set of integers whose sum will come close to but not exceed a specified target S.

Examples:

Example 1

Input: set[] = {45, 34, 4, 12, 5, 2}, S = 42
Output: 41

The subset {34, 5, 2} gives the largest sum 41 which is ≤ S.

Example 2

Input: set[] = {3, 34, 4, 12, 5, 2}, S = 10
Output: 10

The subset {2, 3, 5} sums to 10, which is the maximum possible ≤ S.

Optimized Approach: Meet-in-the-Middle

When N is set at small numbers but still high enough to conduct a brute force, we implement Meet-in-the-Middle.

This solution breaks large problems down into two smaller solvable components, which are solved independently, after which the solutions are integrated in a simple 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))).

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:

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 makes it manageable for N to be increased as far 40, which makes it a perfect choice.

Conclusion:

In conclusion, the Meet-in-the-Middle algorithm is effective for the subset sums problem when N becomes very large for brute force methods, yet manageable for optimization techniques.

By splitting the problem into smaller sizes, calculating the required upper subset sums, sorting the smaller sums, and performing a binary search for the corresponding lower sum yields efficient results with very low complexity.

Next TopicPisano-period-in-cpp

← prev next →