LeetCode #22 Medium

Generate Parentheses

Given n pairs of parentheses, generate all combinations of well-formed parentheses.

backtrackingrecursionstrings

02

Intuition

Generating all 2^(2n) strings and filtering the valid ones works but wastes almost all its effort. Instead, prune during construction: you may open a bracket while opens used is below n, and you may close one only while closes used is strictly below opens used. Those two rules make every leaf a valid string, so nothing is generated and discarded.

How to spot this pattern

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.

03

Approach

1

Encode validity as two counters

Track open and close, the number of each placed so far. A string is well-formed exactly when no prefix has more closes than opens and the totals match — both conditions are enforceable from these two counters alone, with no need to inspect the string.

2

Two guarded branches

If open < n, append (, recurse, and backtrack. If close < open, append ), recurse, and backtrack. It's tempting to build every arrangement first and check validity at the end, but that means generating 2^(2n) strings only to throw most of them away. The close < open guard avoids that entirely — it is what prevents "())" from ever being started, rather than detecting it afterwards.

3

Record at the leaf

When the current string reaches length 2n, it is complete and necessarily valid, so append it to the results. Using a list as a buffer with pop-on-backtrack avoids repeated string concatenation. The number of answers is the nth Catalan number, so the complexity is O(4^n / sqrt(n)) — optimal, since simply emitting the output costs that much.

04

Solution & live demo

▶1class Solution:
▶2    def generateParenthesis(self, n):
▶3        res, buf = [], []
▶4 
▶5        def go(op, cl):
▶6            if len(buf) == 2 * n:
▶7                res.append(''.join(buf))
▶8                return
▶9            if op < n:
▶10                buf.append('(')
▶11                go(op + 1, cl)
▶12                buf.pop()
▶13            if cl < op:
▶14                buf.append(')')
▶15                go(op, cl + 1)
▶16                buf.pop()
▶17 
▶18        go(0, 0)
▶19        return res

05

Common pitfalls

Generating everything and validating

✗ Wrong

for s in product('()', repeat=2*n):
    if valid(s): res.append(s)

✓ Right

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

✗ Wrong

if cl < n:

✓ Right

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

✗ Wrong

buf.append('(')
go(op + 1, cl)

✓ Right

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.

06

Edge cases

n = 1

One answer: "()".

n = 0

One answer, the empty string — worth confirming the base case does not return an empty list.

Dropping the close < open guard

Invalid strings such as ")(" get generated, which is the entire point of the pruning.

Forgetting to backtrack the pop

The buffer leaks characters across branches and every subsequent answer is corrupted.

07

Complexity

Time

O(4^n / sqrt(n))

Space

O(n)

Catalan-many outputs, so this is optimal. Recursion depth is 2n.