STEP 7 · RECURSION · PRUNE ON A PARTIAL · MEDIUM

Generate Parentheses

WHAT IT SAYS

Generate every well-formed string of n pairs of parentheses.

WHAT IT'S REALLY ASKING

"Do not build strings and then judge them. A prefix is already doomed the instant it closes more brackets than it has opened — and no suffix can ever repair that. So the real question is: what is the earliest moment a candidate becomes provably dead, and can you refuse to grow it from there?"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Build all strings, then filter

O(2^(2n) * n) time

Enumerate every string of length 2n over the two characters, then run a validity check on each — a counter that must never go negative and must end at zero — and keep the survivors.

WHERE THE WORK IS WASTED — The check happens at the END, so a prefix that died on character three still gets every one of its completions constructed, one by one, and rejected one by one. Write out '())' and count what brute force does next: it dutifully builds all 2^(2n-3) strings beneath it, each of which was invalid before the loop even started. And the gap is enormous — for n = 10 there are about a million candidates and only 16796 valid answers. You are spending exponential effort to rediscover a fact that a single character already told you.

KEY OBSERVATION — THE UNLOCKlink

Invalidity is inherited: once broken, never repaired.

A parenthesis string is valid exactly when two things hold: every prefix has at least as many opens as closes, and the totals are equal at the end. Look hard at the first condition. It is a statement about PREFIXES, which means it can be evaluated on a half-finished candidate. And it is monotone in the worst way for the candidate: appending characters can only ever increase the close count, never decrease it. So once a prefix has more closes than opens, no continuation on earth brings it back. The verdict 'invalid' is hereditary — every descendant of a dead node is dead. That inheritance is precisely the licence to prune. It is not an optimisation you hope pays off; it is a proof that the entire subtree is empty, so cutting it discards nothing. And once you commit to never generating a dead node, the two extension rules write themselves. You may append '(' only while you still have opens left to spend — open count below n. You may append ')' only while there is something to close — close count strictly below open count. Follow those two rules and every node of your search tree is a valid prefix, every leaf is a valid answer, and not a single candidate is ever rejected. The work becomes proportional to the OUTPUT, not to the candidate space.

Grow only living prefixes

O(Catalan(n) * n) time — proportional to the number of answers, times the cost of writing one down

Recurse carrying the current string and two counters, open and close. If close equals n, the string is complete — record it. Otherwise: if open is below n, append '(' and recurse; if close is below open, append ')' and recurse. Undo the append on the way out. No validity check exists anywhere in the code, because invalid strings are never built.

WHAT YOU TRADED — The pruning is only sound because the violated constraint is unrepairable — if a rule could be broken and later fixed, cutting the subtree would silently lose answers. The transferable lesson: the whole art of backtracking is finding the earliest moment a constraint becomes decidable on a partial solution, and proving that failure at that moment is permanent.

WATCH THE IDEA RUN

THE PARTIAL STRING BEING BUILT

stack empty — every branch explored

VALID RESULTS

—

branches pruned at birth 0

nodes explored 0

brute force would build 64

Generate all 2^(2n) strings of brackets and filter the valid ones: 64 candidates for n=3, of which only 5 survive. The waste is not that we check them — it is that we BUILT them.

step 1 / 37

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Prune at the Earliest Provable Death

YOU'LL SEE IT AGAIN WHEN

A candidate can be judged invalid from a partial prefix, and no extension can repair the violation — the failure is monotone.
The set of valid answers is exponentially smaller than the set of candidates, so generate-and-test is doing almost all of its work on garbage.
You are generating, not counting, so the ideal cost is proportional to the output — any candidate you build and then reject is pure loss.

SAME BLUEPRINT, DIFFERENT PROBLEM

N-QueensSudoku SolverCombination SumWord Search

The bar isn't "solved it once." It's "could rebuild it from the observation."