leetcode 416
You are handed a pile of numbers. Can you deal them into two stacks that weigh exactly the same? People call this a hard problem. It is a scale you can tip with your finger.
Tap any number to send it across. Balance the two pans.
Maya and Theo tip a bag of candy onto the table. The pieces weigh 1, 5, 11, and 5 grams. They want two equal piles, no piece cut in half. Try it in your head before you read on: which pieces go to Maya?
You probably found it fast. The 11 goes to one kid. The 1, 5, and 5 go to the other. Eleven grams each. Nobody cries.
Four bags. Tap one. Green means an even split exists; some bags simply cannot be split.
So the answer is sometimes yes and sometimes no. That "sometimes no" is the whole reason this is a real question and not a party trick. Before we hunt for the yes, there is one bag we can reject without any thinking at all.
Add every piece in the bag. Call it the total. Now say you want two equal piles: each pile has to weigh exactly half of that total. Half of 22 is 11. Fine. But half of 23 is 11.5, and there is no such thing as half a candy.
Push the buttons below. Drop a number in or pull one out and watch the total. The instant the total goes odd, the answer is a flat no, and you did not inspect a single subset to know it.
Toggle numbers in and out of the bag. Odd total: no midpoint, no split. Even total: the target lights up.
Even total, though, is only a hall pass. The bag 1, 2, 5 adds to 8, nicely even, target 4, and it still cannot be split. So an even total gets us to the real question, and the real question is about one pile, not two.
Here is the move that turns this from scary to small. Forget about building two piles. Build only one pile, and try to make it weigh exactly the target. If you can, you are already done, because whatever you left behind is the other pile, and it weighs the total minus the target, which is the target again.
Fill the pan below. Tap pieces into it and chase the line at 11. Land on it exactly and the leftovers light up on their own, already equal.
Tap pieces into the pan. Hit 11 exactly and the leftovers turn out equal by themselves.
Good. The whole problem is now a single sentence: can I pick some of these numbers so they add to the target? The lazy way to answer that is to try every possible pick. Let us see how badly that goes.
Each number has two fates: in the pan, or out. Flip them yourself below. Every pattern of in and out is one subset to test, and the counter shows how many patterns exist. With four numbers it is sixteen. Cute. Now drag the slider.
Tap the tiles to pick a subset. Every extra number doubles the work. At 40 numbers, brute force is hopeless.
The trap in brute force is that it forgets. It rebuilds the sum 6 from scratch a thousand times over. What if, instead of listing every pile, we just kept a running checklist of which totals are even possible?
Start with one honest fact: the sum 0 is reachable, by picking nothing. Now feed in the numbers one at a time. Each number, when it arrives, looks at every sum already on your checklist and adds a fresh option: that sum plus itself. Watch the strip fill as we pour in 1, 5, 11, 5. The moment the target lights up, the answer is yes.
Start: only 0 is reachable.
Before any number, exactly one total is reachable: zero, the empty pan. Everything else is blank.
For every ticked box, tick the box one step to the right. Zero was ticked, so now 1 is too. Reachable: 0, 1.
Copy every tick five boxes right. 0 gives 5, and 1 gives 6. The checklist grows without redoing old work. Reachable: 0, 1, 5, 6.
Copy every tick eleven boxes right. Zero plus eleven is eleven, and eleven is the target. The box turns green. The answer is already yes.
The final 5 fills in a few more boxes, but we were done a step ago. One pass over the numbers, one row of boxes, one clear yes.
Brute force asked "which pile?" over and over. The checklist asks "which sums are possible?" exactly once.
That row of boxes is the entire idea behind the scary phrase. But where do the boxes come from, and why is copying-to-the-right always correct? For that we open the hood and look at the table underneath.
Stack a checklist for each stage. Row 0 is before any number: only sum 0 is reachable. Each later row adds one number to the ones allowed so far. The grid below is that stack for 1, 5, 11, 5. Tap any green cell and it shows you the two cells above it that made it true.
Tap a green cell to see where it came from.
Look closely at a lit cell and you notice something wasteful: every row copies almost all of the row above it, unchanged. We are storing a whole history we never look back at. That waste is an invitation.
Since each row only ever reads the row directly above, throw the history away and keep a single row, updating it in place. There is exactly one trap, and it is worth feeling before you are told. Take one number, a 3, and a fresh row where only 0 is ticked. Apply the 3 two ways below.
Down (right to left): only 3 lights, correct. Up (left to right): 3, 6, 9 light, the 3 got reused.
So the finished machine is tiny: one boolean row, one pass per number, always sweeping downward. That fits in a dozen lines, and it looks almost the same whichever language you reach for.
Step the trace on the right and watch the single row fill exactly as the code says, sweeping each number downward. Then switch languages. Python, Rust, and JavaScript disagree about semicolons and nothing else that matters here.
None of that is bigger than the balance scale you tipped at the top. The fear was about the words, not the work. One honest caveat remains, and it is about size, not difficulty.
The row has one box per sum from 0 to the target, and the target is half the total. Small numbers, short row, instant answer. But scale every number up and the row stretches with them. Slide below and watch the work, which is bag size times target, balloon even though the count of numbers never changed.
Same four numbers, scaled up. The answer is just as easy; the row is not.
For the arrays you meet in an interview, none of that bites. You have a linear-feeling sweep, one row of booleans, and a problem you can now explain to the kid dividing the candy.
the whole thing
The same shape shows up whenever two things must come out even: splitting a bill without a calculator, balancing two servers, dividing work across a night shift. It was never a monster. It was a scale.
press s for the deeper cuts
Subset sum is NP-complete in general, but our row-of-booleans runs in bag size times target time. There is no contradiction: the target can be exponentially large in the number of digits it takes to write it down. When the values are small the target is small and the trick is fast; when the values can be gigantic, the row can be gigantic too. The short code is fast in the value, not fast in the input length, which is exactly what "pseudo polynomial" means.
A reachable-sums row is a row of bits, and copying every tick k boxes to the right is a left shift by k followed by an OR with itself. In Python that is one line: bits |= bits << x on a big integer, then check bit number target. It does the same work the loop does, but the machine moves 64 sums per instruction, so it is often an order of magnitude faster with no change to the idea.
When you update box t you read box t minus x. Sweeping from high t to low t, box t minus x has not been touched yet this pass, so it still reflects the row before this number arrived, meaning this number is counted at most once. Sweeping the other way, box t minus x may already include this same number, which is how a single 3 climbs to 6 and 9. The direction is the proof.
The boolean row answers yes or no. To hand Maya her exact pieces, keep the 2D table (or a parent pointer per cell) and walk backward from the target box in the last row: at each step, if the sum was reachable without the current number, step up; otherwise take that number into the pile and subtract it. You arrive at 0 holding one valid half.