Brute-force search can run out of room long before the code itself gets hard to read. Meet-in-the-middle handles that pressure by cutting the input into two halves, finding the possible totals from each side, and then pairing those totals to reach the target. For subset sum, that changes the search from checking every possible full subset across 2^n choices into building two smaller collections near 2^(n / 2) in size. The algorithm still has exponential cost, so it does not turn every hard search problem into a small one, but it can bring a case that is too large for direct brute force into a range where memory and runtime are far more manageable.
How the Split Reduces Search
Meet-in-the-middle starts from a practical search problem. Some inputs create too many combinations for direct brute force, even when the code is easy to read. Splitting the input does not remove the exponential cost, but it changes the size of the search the code has to handle. We build partial choices from the left side, build partial choices from the right side, and then join matching results instead of testing every full choice directly.
Why the Search Space Shrinks
Full subset search grows by doubling. If the input has n numbers, every number has two choices. We either include that number in the subset or leave it out. That gives 2^n possible subsets. Small inputs are fine for direct brute force, but the count rises fast as n grows. With n = 40, direct brute force has 2^40 possible subsets, which is 1,099,511,627,776 choices. That is far beyond a reasonable amount of direct subset checking.
Meet-in-the-middle changes the search by cutting the input near the center. The left half has about n / 2 numbers, and the right half has the rest. Each half then has about 2^(n / 2) subset sums. With n = 40, each half has about 2^20 sums, which is 1,048,576 sums per side. That is still a large collection of partial results, but it is nowhere near 2^40. The algorithm pays for two smaller exponential searches instead of one enormous search across the whole input. That difference is the reason this technique can fit medium-sized input limits where direct brute force fails.
We can compare the counts directly before talking about the full algorithm:
public class SplitSearchCounts {
public static void main(String[] args) {
int n = 40;
long bruteForceChoices = (long) Math.pow(2, n);
long halfChoices = (long) Math.pow(2, n / 2);
System.out.println(bruteForceChoices);
System.out.println(halfChoices);
}
}The first value represents every subset across the whole input. The second value represents every subset for one half. Meet-in-the-middle normally stores partial results from both halves, so the rough stored count is closer to 2 * 2^(n / 2), but that is still far smaller than 2^n as the input grows.
The split also changes how we think about a full answer. Instead of trying every subset from all numbers, we make every possible partial result from the left side and every possible partial result from the right side. Then a full answer can come from one left result paired with one right result. For subset sum, the full subset can be divided into two pieces. Some chosen values come from the left half, and some chosen values come from the right half. The algorithm does not need to know those choices ahead of time. It only needs to know the totals each side can produce.
The two halves stay independent while we generate their totals. The left side does not need to know which values from the right side will be chosen while it builds its sums. The right side follows the same idea. The connection happens later, when the algorithm searches for two partial sums that reach the target.
Partial Results From Each Half
Stored partial results form the bridge between the split input and the final answer. In subset sum, a partial result is just a sum made from one side of the array. In related problems, a partial result can carry other data, such as the count of selected values or a total weight, but subset sum keeps the first version easy to follow.
The match is based on addition. If the left half can make leftSum, then the right half needs to make target - leftSum. When that needed value appears in the right-side results, both halves form a full subset that reaches the target.
Take this input:
[3, 34, 4, 12, 5, 2]Target:
9The left half can be [3, 34, 4], and the right half can be [12, 5, 2]. The left half can make sums such as 0, 3, 34, 37, 4, 7, 38, and 41. The right half can make sums such as 0, 12, 5, 17, 2, 14, 7, and 19.
The target 9 can be formed by 7 from the left half and 2 from the right half. The full subset is [3, 4, 2].
We can see the matching rule with a small Java fragment:
long target = 9;
long leftSum = 7;
long neededFromRight = target - leftSum;
System.out.println(neededFromRight);The printed value is 2, so a right-side partial sum of 2 completes the target. The algorithm repeats that same calculation for the left-side sums.
The right-side list is usually sorted before lookup. Sorting lets the code use binary search, which checks for the needed value in O(log m) time, where m is the number of right-side sums. The left-side sums can be scanned from beginning to end. For each left value, we compute the missing amount and search the sorted right-side list.
long[] rightSums = {0, 12, 5, 17, 2, 14, 7, 19};
Arrays.sort(rightSums);
long needed = 2;
int index = Arrays.binarySearch(rightSums, needed);
System.out.println(index >= 0);The result is true because the right side can contribute 2. The exact index does not matter for a yes-or-no subset-sum check. Finding the value is enough.
This is where the two halves meet because each side was generated without depending on the other side, then the matching step asks which pair of partial results forms the target. That pairing is much cheaper than building every full subset directly when the input is large enough for the split to pay off.
The time cost has three main parts. Generating the partial sums takes O(n * 2^(n / 2)) with the common bitmask style because every mask checks the values inside its half. Sorting one side takes O(2^(n / 2) log 2^(n / 2)). Searching for each left sum inside the right list also takes O(2^(n / 2) log 2^(n / 2)).
Those terms are commonly written as O(n * 2^(n / 2)), because log 2^(n / 2) grows in proportion to n. The space cost is O(2^(n / 2)), because the algorithm stores partial sums for the halves.
Meet-in-the-middle helps with medium-sized brute-force searches because it reduces the exponent in the search count. It does not turn an exponential problem into a polynomial one, but it changes the brute-force limit enough to make some inputs practical.
Java Subset Sum Example
The Java version takes the split-and-match idea and turns it into a complete subset-sum check. We divide the array into two ranges, generate every subset sum from both ranges, sort the second collection, then scan the first collection for a matching complement. The full subset does not need to be built while the search runs. We only need enough information to tell which totals can come from the left side and which totals can come from the right side.
Building Subset Sums
The helper method receives a start index and an end index, so it can build totals from only part of the array. That keeps the split visible in the code. The left call handles indexes from 0 up to mid, and the right call handles indexes from mid up to nums.length. For each half, a bitmask represents the values selected for a subset. If the half has three values, there are eight possible masks. The mask 0 selects nothing, while the mask with all three low bits turned on selects every value in that half. Every mask maps to a subset total.
We can write the helper so the range controls which part of the array gets read:
private static long[] subsetSums(int[] nums, int start, int end) {
int length = end - start;
int totalMasks = 1 << length;
long[] sums = new long[totalMasks];
for (int mask = 0; mask < totalMasks; mask++) {
long sum = 0L;
for (int bit = 0; bit < length; bit++) {
if ((mask & (1 << bit)) != 0) {
sum += nums[start + bit];
}
}
sums[mask] = sum;
}
return sums;
}The outer loop walks through every possible selection inside the given range. The inner loop checks which bits are turned on for the current mask. If bit 0 is turned on, we add the first value in that half. If bit 1 is turned on, we add the second value in that half, and the same rule continues through the range.
The start + bit expression lets the same method build totals for either side. With start = 0, it reads from the left side of the array. With start = mid, it reads from the right side. The method does not need a separate flag for left or right because the range already gives it that information.
The full solver can call that helper twice:
int mid = nums.length / 2;
long[] leftSums = subsetSums(nums, 0, mid);
long[] rightSums = subsetSums(nums, mid, nums.length);The split does not need to be perfectly equal for odd input lengths. If the array has seven values, the left side gets three values and the right side gets four values with this mid calculation. That is fine because the ranges still cover the entire array without overlap.
The bitmask count comes from 1 << length, which means 2^length. That expression is fine while length stays within a small range. Larger halves need more care because the number of masks grows fast and the array of totals can become too large to allocate.
The main method below places the sum builder inside the full yes-or-no subset sum check:
import java.util.Arrays;
public final class MeetInTheMiddleSubsetSum {
public static boolean hasSubsetSum(int[] nums, long target) {
int mid = nums.length / 2;
long[] leftSums = subsetSums(nums, 0, mid);
long[] rightSums = subsetSums(nums, mid, nums.length);
Arrays.sort(rightSums);
for (long leftSum : leftSums) {
long needed = target - leftSum;
if (Arrays.binarySearch(rightSums, needed) >= 0) {
return true;
}
}
return false;
}
private static long[] subsetSums(int[] nums, int start, int end) {
int length = end - start;
if (length > 25) {
throw new IllegalArgumentException();
}
int totalMasks = 1 << length;
long[] sums = new long[totalMasks];
for (int mask = 0; mask < totalMasks; mask++) {
long sum = 0L;
for (int bit = 0; bit < length; bit++) {
if ((mask & (1 << bit)) != 0) {
sum += nums[start + bit];
}
}
sums[mask] = sum;
}
return sums;
}
public static void main(String[] args) {
int[] nums = {3, 34, 4, 12, 5, 2};
System.out.println(hasSubsetSum(nums, 9));
System.out.println(hasSubsetSum(nums, 30));
}
}The first call prints true, because the values 3, 4, and 2 can reach 9. The second call prints false, because the array has no subset that reaches 30.
This exact-equality version also handles negative numbers. Sorting and binary search still behave normally with negative totals. Related versions, such as finding the best total under a maximum limit, need different matching logic, but exact subset sum only needs to check for target - leftSum.
Sorting the Second Half
The right-side totals are sorted so the match step can search them quickly. The left-side totals do not need sorting for this yes-or-no version because we scan them from beginning to end. For every leftSum, the code calculates the amount needed from the right side and checks the sorted right-side array.
Arrays.sort(rightSums);
for (long leftSum : leftSums) {
long needed = target - leftSum;
if (Arrays.binarySearch(rightSums, needed) >= 0) {
return true;
}
}The search step is based on complements. If target is 9 and the current left total is 7, then the right side needs 2. If the sorted right-side array contains 2, the two halves form the target.
Arrays.binarySearch returns a nonnegative index when it finds the value. If the value is absent, it returns a negative number. The exact index does not affect this yes-or-no check because finding the value is enough. Duplicate totals can appear in either half. Two different subsets can produce the same total, and that does not hurt the algorithm. If the right-side array contains the needed value at least once, the answer is still true.
The right-side sort also keeps the code away from nested loops over both arrays. Without sorting, checking every left total against every right total would lead to about 2^(n / 2) * 2^(n / 2) comparisons, which returns to 2^n behavior. Sorting gives a faster match step because each left total searches the right side in logarithmic time.
The match step only cares about presence:
long[] rightSums = {0, 12, 5, 17, 2, 14, 7, 19};
Arrays.sort(rightSums);
System.out.println(Arrays.binarySearch(rightSums, 2) >= 0);
System.out.println(Arrays.binarySearch(rightSums, 6) >= 0);The first print call returns true because 2 exists in the sorted array. The second returns false because 6 does not appear as a right-side subset total. The same rule applies inside the full method. Each left total asks for exactly one right total, not every possible right total. That is where sorting pays off.
Why long Helps
The input array uses int, but the totals use long. That choice is helpful because subset totals can exceed the range of int even when every individual input value fits inside int.
Java int values range from -2,147,483,648 to 2,147,483,647. If a subset contains several large positive values, the total can pass that upper limit. With int totals, the value wraps around and the result can become wrong without any compiler error.
This short calculation shows the difference between adding as int and adding as long:
int first = 1_600_000_000;
int second = 1_600_000_000;
int intSum = first + second;
long longSum = (long) first + second;
System.out.println(intSum);
System.out.println(longSum);The intSum value overflows because the result is too large for int. The longSum calculation stores the expected total because the first value is converted before the addition happens.
The subset sum helper follows the safer form by declaring sum as long:
long sum = 0L;
for (int bit = 0; bit < length; bit++) {
if ((mask & (1 << bit)) != 0) {
sum += nums[start + bit];
}
}The array of totals is also a long[], so the values keep that larger range after they are stored. The target is a long too, which keeps the subtraction in the match step aligned with the stored sums.
long needed = target - leftSum;This does not mean every numeric case is safe forever though. A long can also overflow if the values or selected item count are large enough. Still, for this algorithm style, long is the better default for totals because the sum can grow beyond the original item type.
The mask count is separate from the sum type. long helps store larger totals, but it does not reduce the number of subsets. The expression 1 << length still grows as 2^length, so memory remains the limiting factor for large halves.
Runtime Boundaries
The runtime comes from three parts of the method. First, the code generates all totals from the left half and all totals from the right half. Then it sorts the right-side totals. Last, it scans the left-side totals and performs binary search for each complement.
For n input values, each half has about n / 2 values. Each half creates about 2^(n / 2) totals. With the bitmask helper shown earlier, each mask can check up to half the input, so sum generation costs O(n * 2^(n / 2)).
Sorting the right-side array costs O(2^(n / 2) log 2^(n / 2)). The binary-search pass has the same logarithmic factor because every left-side total searches inside the sorted right-side array.
Separated by phase, the cost reads like this:
sum generation: O(n * 2^(n / 2))
right-side sort: O(2^(n / 2) log 2^(n / 2))
matching search: O(2^(n / 2) log 2^(n / 2))Those terms are commonly reduced to O(n * 2^(n / 2)), because log 2^(n / 2) grows in proportion to n. The space cost is O(2^(n / 2)), because the method stores the partial totals for the two halves.
The guard inside the helper is there for memory. It stops the method from trying to allocate a huge array when a half is too large.
if (length > 25) {
throw new IllegalArgumentException();
}With length = 25, one half has 33,554,432 possible totals. A long[] that large takes a lot of memory. Two halves can take far more, and the sort also needs room to run. The exact limit depends on the environment, but the growth rate is the important part.
Meet-in-the-middle trades direct brute-force time for stored partial results. Direct brute force can avoid saving huge arrays, but it has to check the full 2^n search space. Meet-in-the-middle stores half-sized result collections so the match step can run much faster than a full nested search.
The code uses a readable bitmask builder, so its generation cost includes a loop over the bits for every mask. Faster generation styles can update sums from earlier masks, but the same main boundary remains. The number of partial results still grows as 2^(n / 2), and that growth controls both time and memory.
Conclusion
Meet-in-the-middle gets its value from the split. We turn one large 2^n search into two smaller 2^(n / 2) result collections, then let sorting and binary search bring the halves back into contact. For subset sum, that means the left side gives us leftSum, the right side only has to contain target - leftSum, and the full answer comes from that match. The cost is still exponential, with O(n * 2^(n / 2)) time and O(2^(n / 2)) space, but the mechanics make a direct brute-force search much more practical for input sizes where the full search would be too large.
Java
ArraysAPI Documentation
Thanks for reading! If you found this helpful, highlighting, clapping, or leaving a comment really helps me out.