Chapter 6.4: Meet in the Middle

English translation of this chapter is coming soon. Please refer to the Chinese version for now.

Content Outline

6.4.1 Problem Introduction: Subset Sum

• Brute Force: O(2^N) for N up to 40 is Infeasible

6.4.2 Core Idea of Meet in the Middle

• Split N Elements into Two Halves
• Enumerate Each Half Separately, Then Merge
• Time Complexity: O(2^(N/2) x N)

6.4.3 Complete Implementation: Subset Sum Existence

6.4.4 Counting Variant: Number of Subsets with Exact Target Sum

6.4.5 Maximum Subset Sum Variant (Sum Not Exceeding Target)

6.4.6 Meet in the Middle vs Other Methods

• Comparison Table: Brute Force / Meet in the Middle / DP (Knapsack) / 2D DP
• Applicable Conditions

Common Mistakes

Exercises

1. Subset Sum Existence
2. Subset Sum Counting (mod 10^9+7)
3. Closest Subset Sum to Target
4. USACO Gold Style — Optimal Pairing