LeetCode 22 ·
Medium
Generate Parentheses
Generate all combinations of n well-formed parentheses.
Try it
Step through the core mechanic. The simulator below runs the backtracking shape this problem is built on.
Interactive · Recursion call tree — Fibonacci naive recomputes; memoised short-circuits on cache hits
Mode O(2ⁿ) calls
enter fib(6)
total calls1 unique values≤ 7 modenaive
Toggle the modes.
Naive at n=6 makes 25 calls. Memoised at n=6 makes 11 calls — and the cache
hits (amber circles) are the difference. The shape of the tree changes
dramatically: naive is a fat exponential tree; memoised collapses to a
near-linear path with stub returns where the cache hits.
The approach
Backtrack with counts of open and close used. Add "(" while open < n; add ")" only while close < open. When length hits 2n the string is complete and valid by construction.
| Aspect | Value |
|---|---|
| Pattern | Backtracking |
| Recognise it by | Enumerate all valid bracket strings of n pairs. |
| Time complexity | O(4ⁿ/√n) |
| Space complexity | O(n) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.