Generate Parentheses
Build only well-formed strings of n pairs, using two guards instead of generating and filtering.
Examples
The five well-formed strings of three pairs — Catalan(3).
One pair, one way to write it.
Problem Understanding
List every string that uses exactly n opening and n closing parentheses and is well formed, meaning no prefix ever closes more brackets than it has opened.
Example: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Algorithm Strategy
Instead of generating all 2²ⁿ strings and validating them, we can build only valid strings.
Rules:
- Open: We can add an open parenthesis
(ifopen_count < n. - Close: We can add a closing parenthesis
)ifclose_count < open_count.
This ensures we never close more than we open (validity) and never exceed n (completeness).
Interactive Visualization
Every node is one call to backtrack(open, close). Its label is the bracket that call added, and the pair under it is opened, closed — the two counts the guards test. ( branches go left and ) branches go right.
A call with only one child is a guard that said no, and the figure stops on that check as a step of its own: no ( once all n are open, and no ) when there is nothing open to close. The bottom row is the answer, in the order the code returns it.
Dry Run
Tracing n = 2.
| # | Call | Path | What happens |
|---|---|---|---|
| 1 | backtrack(0, 0) |
"" |
0 < 2: add ( → backtrack(1, 0) |
| 2 | backtrack(1, 0) |
( |
1 < 2: add ( → backtrack(2, 0) |
| 3 | backtrack(2, 0) |
(( |
2 < 2 fails — no (. 0 < 2: add ) → backtrack(2, 1) |
| 4 | backtrack(2, 1) |
(() |
No (. 1 < 2: add ) → backtrack(2, 2) |
| 5 | backtrack(2, 2) |
(()) |
Length 4: record (()), return |
| 6 | backtrack(2, 1), then backtrack(2, 0) |
(( |
Pop ) twice — both return |
| 7 | backtrack(1, 0) |
( |
Pop (. 0 < 1: add ) → backtrack(1, 1) |
| 8 | backtrack(1, 1) |
() |
1 < 2: add ( → backtrack(2, 1) |
| 9 | backtrack(2, 1) |
()( |
No (. 1 < 2: add ) → backtrack(2, 2) |
| 10 | backtrack(2, 2) |
()() |
Length 4: record ()(), return |
| 11 | backtrack(1, 1) |
() |
Pop (. 1 < 1 fails — no ). Return |
| 12 | backtrack(0, 0) |
"" |
Pop (. 0 < 0 fails — no ). Return |
Result: ["(())", "()()"] — every string was valid when it was built, so nothing was generated and thrown away.
Edge Cases & Common Mistakes
Watch out for these pitfalls:
The 'Random String' trap: A common brute force mistake is generating all 2²ⁿ strings of '(' and ')' and checking validity. That is O(n × 4ⁿ) work for only Catalan(n) answers. Backtracking is vastly superior.
Base Case Confusion: Remember the base case is when
open == nandclose == n(string length 2n). Don't stop just because you can't add more open brackets.Strict Order: You can NEVER add a closing parenthesis if
close >= open. This simple rule guarantees validity.
Solution
One algorithm in all six languages — the lines light up as the figure above steps.
Generate Parentheses Code
1var generateParenthesis = function(n) {2 const result = [];3 const path = [];45 const backtrack = (openCount, closeCount) => {6 if (path.length === 2 * n) {7 result.push(path.join(''));8 return;9 }10 if (openCount < n) {11 path.push('(');12 backtrack(openCount + 1, closeCount);13 path.pop();14 }15 if (closeCount < openCount) {16 path.push(')');17 backtrack(openCount, closeCount + 1);18 path.pop();19 }20 };2122 backtrack(0, 0);23 return result;24};