Generate Parentheses
Given n pairs of parentheses, generate all combinations of well-formed parentheses.
- 1 <= n <= 8
Intuition
Generate parentheses produces all well-formed combinations of n pairs of brackets. Generating every arrangement of n opens and n closes and filtering the valid ones works, but wastes most of its effort — the Catalan number of valid strings is far smaller than the 2^(2n) arrangements.
The better approach never builds an invalid string. At each position the choice is to add ( or ), and two simple rules decide which are legal:
- An open bracket is allowed while fewer than n have been used; a close bracket is allowed only while closes are strictly fewer than opens.
That second rule is what guarantees well-formedness. Every close bracket has an unmatched open before it, so the string can never go negative — and no validity check is needed at the end, because invalid strings are never constructed.
Tracking two counters, opens used and closes used, is enough. The current string length is their sum, so no separate index is needed.
The base case is a string of length 2n, at which point both counters equal n and the combination is complete. Recording it there requires no verification.
Because strings are immutable in most languages, the recursion carries a new string per call and needs no explicit undo. With a mutable character list, the usual backtracking rule applies — remove the appended character after recursing, or sibling branches inherit corrupted state.
The count of results is the n-th Catalan number, which bounds the work: no algorithm can beat the output size.
Prune instead of filter. Rather than generating all 2^(2n) strings and validating each, two counters make invalid states unreachable: open a bracket while open < n, close one while close < open. The validity rule becomes the branching rule, so every leaf reached is an answer.
Approach
Before reading on: price up what counting everything costs here, then ask what has to be undone after each choice so the next branch starts clean. Aim for O(4^n / sqrt(n)) time and O(n) space.
Avoid generating invalid strings
Filtering all 2^(2n) arrangements wastes most of the work. Constructing only valid strings cuts the search to the Catalan number of actual answers.
Track opens and closes used
Two counters describe the whole state — the string's length is their sum, so no separate position index is needed.
Allow an open while under the limit
Add ( whenever fewer than n opens have been used. This is the only condition an opening bracket must satisfy.
Allow a close only behind an open
Add ) only while closes are strictly fewer than opens. This single rule guarantees well-formedness — the string can never go negative.
Record at full length
When the string reaches 2n characters, both counters equal n and the combination is complete. No validity check is needed, since invalid strings were never built.
Undo only with mutable state
Immutable strings need no cleanup, since each call carries its own copy. With a character list, remove the appended character after recursing or siblings inherit corrupted state.
Cost of the generation
The result count is the n-th Catalan number, roughly O(4ⁿ / n^1.5), each of length 2n. No algorithm beats the output size; space is O(n) for the recursion depth.
Solution & live demo
Common pitfalls
Generating everything and validating
for s in product('()', repeat=2*n):
if valid(s): res.append(s)if op < n: ... if cl < op: ...
That explores 2^(2n) strings to find only the Catalan number of them — for n = 8, about 65,000 candidates for 1,430 answers. Encoding validity in the branch conditions means no wasted subtree is ever entered.
Closing based on n rather than open count
if cl < n:
if cl < op:
cl < n permits ")(" — a closing bracket with nothing open. The invariant that makes a prefix extendable is that closes never exceed opens so far, which is exactly cl < op.
Forgetting to pop after recursing
buf.append('(')
go(op + 1, cl)buf.append('(')
go(op + 1, cl)
buf.pop()The shared buffer must be restored to its pre-call state before trying the sibling branch, or the second branch builds on top of the first's leftovers. Every append in a backtracking search needs its matching pop.
Edge cases
One answer: "()".
One answer, the empty string — worth confirming the base case does not return an empty list.
Invalid strings such as ")(" get generated, which is the entire point of the pruning.
The buffer leaks characters across branches and every subsequent answer is corrupted.