Knowledge Guide
Home › DSA › Advanced Patterns

Introduction to Meet in the Middle

Meet In the Middle approach is particularly useful when the problem space is too large for a brute force solution but can be efficiently narrowed down by dividing it into smaller, more manageable parts.

The core idea behind the "Meet In the Middle" pattern is to split the problem into two halves and solve each half independently. The solutions of these halves are then combined or "met in the middle" to produce the final solution. By breaking down the problem, the pattern significantly reduces the time complexity compared to a full brute-force search.

Let's illustrate the "Meet In the Middle" approach with the following problem:

Problem Statement

Given a set of n integers where n <= 40, and each integer is at most 1012, determine the maximum sum subset with a sum less than or equal to S, where S <= 1012.

Why Not Brute Force?

Step-by-Step Explanation of "Meet In the Middle" with Code Example

Let's walk through the "Meet In the Middle" algorithm using the example array int[] nums = {3, 15, 14, 9, 6, 2} with long S = 10. We'll explain each step of the algorithm and show how it is applied to this example.

Step 1: Splitting the Array into Two Halves

The first step in the "Meet In the Middle" approach is to divide the original array into two halves.

Code:

int[] nums = {3, 15, 14, 9, 6, 2};
int n = nums.length;
int mid = n / 2;

int[] left = Arrays.copyOfRange(nums, 0, mid);
int[] right = Arrays.copyOfRange(nums, mid, n);
Image
Image

Step 2: Generate All Possible Subset Sums for Both Halves

Next, we generate all possible subset sums for both the left and right halves.

Code:

List<Long> sumLeft = generateSubsetSums(left);  // Subsets of {3, 15, 14}
List<Long> sumRight = generateSubsetSums(right);  // Subsets of {9, 6, 2}
Image
Image

Step 3: Sort the Subset Sums of the Right Half

To facilitate efficient searching, we sort the sumRight list.

Code:

Collections.sort(sumRight);

Explanation: Sorting sumRight allows us to efficiently search for the best complementary sum using binary search.

Step 4: Find the Maximum Subset Sum Less than or Equal to S

For each sum in sumLeft, we find the best complementary sum in sumRight such that their combined sum is less than or equal to S.

Code:

long maxSum = 0;

for (long sLeft : sumLeft) {
    if (sLeft > S) continue; // Skip if sLeft alone exceeds S

    long remaining = S - sLeft;

    int idx = upperBound(sumRight, remaining);  // Binary search in sumRight

    if (idx >= 0) {
        long sRight = sumRight.get(idx);
        long total = sLeft + sRight;
        if (total > maxSum) {
            maxSum = total;
        }
    }
}
Image
Image

Code

java
import java.util.*;

public class Solution {

  /**
   * Finds the maximum subset sum less than or equal to S.
   */
  public long maxSubsetSum(int[] nums, long S) {
    int n = nums.length;
    int mid = n / 2;

    // Split the array into two halves
    int[] left = Arrays.copyOfRange(nums, 0, mid);
    int[] right = Arrays.copyOfRange(nums, mid, n);

    // Generate all possible subset sums for both halves
    List<Long> sumLeft = generateSubsetSums(left);
    List<Long> sumRight = generateSubsetSums(right);

    // Sort the sums of the right half for binary search
    Collections.sort(sumRight);

    long maxSum = 0;

    // For each sum in the left half, find the best complementary sum in the right half
    for (long sLeft : sumLeft) {
      if (sLeft > S) continue; // Skip if sLeft alone exceeds S

      long remaining = S - sLeft;

      // Binary search to find the largest sum in sumRight <= remaining
      int idx = upperBound(sumRight, remaining);

      if (idx >= 0) {
        long sRight = sumRight.get(idx);
        long total = sLeft + sRight;
        if (total > maxSum) {
          maxSum = total;
        }
      }
    }

    return maxSum;
  }

  /**
   * Generates all possible subset sums of the given array.
   *
   * @param arr Input array.
   * @return List of subset sums.
   */
  private static List<Long> generateSubsetSums(int[] arr) {
    int len = arr.length;
    int totalSubsets = 1 << len; // 2^len subsets
    List<Long> subsetSums = new ArrayList<>();

    // Iterate over all possible subsets
    for (int mask = 0; mask < totalSubsets; mask++) {
      long sum = 0;
      for (int i = 0; i < len; i++) {
        // Check if the i-th element is included in the current subset
        if ((mask & (1 << i)) != 0) {
          sum += arr[i];
        }
      }
      subsetSums.add(sum);
    }

    return subsetSums;
  }

  /**
   * Finds the index of the largest value less than or equal to target.
   */
  private static int upperBound(List<Long> list, long target) {
    int low = 0;
    int high = list.size() - 1;
    int result = -1;

    while (low <= high) {
      int mid = low + (high - low) / 2;
      if (list.get(mid) <= target) {
        result = mid; // Potential candidate
        low = mid + 1; // Try to find a larger value
      } else {
        high = mid - 1; // Look for smaller values
      }
    }

    return result;
  }

  // Example usage
  public static void main(String[] args) {
    int[] nums = { 3, 15, 14, 9, 6, 2 };
    long S = 10;
    Solution sol = new Solution();
    long result = sol.maxSubsetSum(nums, S);
    System.out.println("Maximum subset sum <= " + S + " is: " + result); // Output should be 9
  }
}

Complexity Analysis

Time Complexity

Space Complexity

Why Use This Technique?

Scenarios Where "Meet In the Middle" Shines

Limitations

Scenarios Where MITM Might Not Be Best

Potential Challenges

Now, let's start solving problems of Meet In the Middle pattern.

🤖 Don't fully get this? Learn it with Claude

Stuck on Introduction to Meet in the Middle? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Introduction to Meet in the Middle** (DSA) and want to truly understand it. Explain Introduction to Meet in the Middle from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Introduction to Meet in the Middle** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Introduction to Meet in the Middle** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Introduction to Meet in the Middle** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Bucket Sort AlgorithmIntroduction to MO’s Algorithm Pat →