Skip to main content
← All Solvers

# ⚖️ Subset Sum

Band 3 — The Luna transformer. Find a subset of numbers that sums to a target.

Numbers: 20
Ready
Numbers in set
Target sum:

### Algorithm: Meet-in-the-Middle

Split the set in half. Enumerate all 2^(n/2) subset sums for each half. Sort one list, then for each sum in the other, binary search for the complement (target − sum). O(2^(n/2) log n) time, O(2^(n/2)) memory. Practical for n up to ~40.

### Why This Matters

Subset Sum is the Luna transformer — it governs division, allocation, and balance. Every partitioning problem (data splitting, load balancing, resource allocation) maps to this.