Generate Parentheses medium
Description
Given n pairs of parentheses, generate all combinations of well-formed parentheses.
Examples
> Case 1:
Input: n = 1
Output: ["()"]
> Case 2:
Input: n = 2
Output: ["(())", "()()"]
> Case 3:
Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]Constraints
1 <= n <= 8
Intuition — naive vs smart
The naive approach: generate every possible string of 2n parentheses, then filter for the valid ones. That’s 2^(2n) strings — way too many.
The smart approach: only generate strings that can still become valid. We build the string one character at a time, and at each step decide whether to add ( or ). We can keep two counters:
open— the number of(we’ve placed so far.close— the number of)we’ve placed so far.
Two rules let us prune branches that can’t possibly be valid:
- We can add
(only ifopen < n— otherwise we’d exceednpairs. - We can add
)only ifclose < open— otherwise we’d close more than we’ve opened (immediately invalid).
This is backtracking — try a choice, recurse, then untry. The key trick is the pruning, which collapses the search space from 2^(2n) to roughly the Catalan number C_n.
Algorithm
backtrack(current, open, close):
if length(current) == 2n:
record current
return
if open < n: backtrack(current + '(', open + 1, close)
if close < open: backtrack(current + ')', open, close + 1)That’s it. No filter at the end — the pruning guarantees every string we record is valid.
Trace for n = 2
backtrack("", 0, 0)
├── add '(' → backtrack("(", 1, 0)
│ ├── add '(' → backtrack("((", 2, 0)
│ │ └── add ')' → backtrack("(()", 2, 1)
│ │ └── add ')' → backtrack("(())", 2, 2) → RECORD "(())"
│ └── add ')' → backtrack("()", 1, 1)
│ └── add '(' → backtrack("()(", 2, 1)
│ └── add ')' → backtrack("()()", 2, 2) → RECORD "()()"
└── (no other choices — close < open is false at root)Two results, zero wasted work.
Code
The backtracking template (modify-recurse-undo) is the same in every language. In Python we use string immutability to “undo” for free — every recursive call gets a fresh string. In C++/Java we share a mutable buffer for speed, so we have to manually pop_back after each call. Pick whichever feels cleaner.
Why this is much faster than 2^(2n)
The number of valid sequences is the n-th Catalan number C_n = (2n)! / ((n+1)! · n!). For small n:
| n | Catalan C_n | 2^(2n) (naive) |
|---|---|---|
| 1 | 1 | 4 |
| 3 | 5 | 64 |
| 5 | 42 | 1,024 |
| 8 | 1,430 | 65,536 |
| 12 | 208,012 | 16,777,216 |
Pruning saves us orders of magnitude of work. This is the whole point of backtracking — explore only the paths that could possibly lead to a solution.
Analysis
- Time: O(4^n / √n) — proportional to the Catalan number
C_n, the number of valid outputs. - Space: O(n) for the call stack and the current string (plus the output array, which we have to produce anyway).