Generate valid sequences

55 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Write every correctly balanced string made of 2 pairs of brackets. By hand: (()) and ()(). For 3 pairs: ((())), (()()), (())(), ()(()), ()()(). Five of them. You could also list all strings of 3 opens and 3 closes, 20 of them, and throw away the unbalanced ones like ())(() . That works for 3 pairs. For 10 pairs there are 184,756 strings with 10 of each and only 16,796 balanced ones; most of the work would be generating junk.

The better way is to never write a wrong character. A string is balanced if, reading left to right, the count of ( never falls below the count of ), and they end equal.

Build the structure, one piece at a time

Piece one: the string being built, as a stack of characters.

Piece two: two counters, opens and closes, how many of each are in the string so far.

Piece three: the two rules that decide what may be appended. You may append ( while opens < n. You may append ) only while closes < opens. That second rule is the entire trick: a ) is allowed only if there is an unmatched ( waiting for it.

Piece four: build(): if the string has length 2n, record it. Otherwise, if ( is allowed, push it, recurse, pop. Then, if ) is allowed, push it, recurse, pop.

Why it is correct

The invariant: every prefix of the string has at least as many ( as ). Appending ( obviously keeps it. Appending ) is only done when closes < opens, so after it closes ≤ opens still holds. A string of length 2n built this way has opens = n (we stop adding at n) and therefore closes = n, and every prefix is fine, which is exactly the definition of balanced. Conversely every balanced string can be built, because at each of its positions the character it has is one the rules allow. So the output is exactly the set of balanced strings, each once.

Why it is fast

The rules prune so hard that every path through the recursion ends in a valid string; there are no dead ends at all. The number of outputs is the Catalan number

C_n = (2n choose n) / (n + 1), so C₂ = 2, C₃ = 5, C₁₀ = 16,796

and each costs 2n characters to write, so the work is about n · C_n, the size of the answer itself. Generate-and-filter would cost the much larger binomial count.

How to recognise it in an interview

Cues: "generate all valid", "well-formed", "every prefix must satisfy", "build strings character by character under a rule". The first thing to say: "I will only append characters that keep the prefix valid, so every leaf is an answer." Generate Parentheses is the example above. Restore IP Addresses uses the same shape with "the next part must be 0 to 255 without leading zeros" as the rule. Remove Invalid Parentheses runs the same validity counter while deciding, for each character, whether to keep or drop it.

02The idea in one line

Add '(' while opens remain; add ')' only while closes < opens.

Reach for it when: Generate parentheses, remove invalid parentheses, letter combinations.

Cost: Catalan(n) outputs.

03The walk-through, step by step

The video works one example: Generate Parentheses n=2. These are its captions in order, so you can follow without the video or check a step you missed.

1. Add '(' while opens < n; add ')' only while closes < opens
2. opens = 0 < 2: add '('
3. opens = 1 < 2: add '('
4. opens = 2: no more '(' allowed
5. closes = 0 < opens = 2: add ')'
6. opens = 2: no more '(' allowed
7. closes = 1 < opens = 2: add ')'
8. Length 4 reached: (()) is valid by construction
9. closes = 0 < opens = 1: add ')'
10. opens = 1 < 2: add '('
11. opens = 2: no more '(' allowed
12. closes = 1 < opens = 2: add ')'
13. Length 4 reached: ()() is valid by construction
14. closes = opens = 1: a ')' here would be invalid, prune
15. closes = opens = 0: a ')' here would be invalid, prune
16. Exactly 2 strings: (()) and ()(), the Catalan number C₂
17. Output count is Catalan(n); each string costs O(n)

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Backtracking: Subsets (include / exclude), Permutations with a used set, Combination sum with a start index, Grid DFS with undo, Constraint placement with pruning.