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.

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

python

▶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

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.

06

Complexity

Time

O(4^n / sqrt(n))

Space

O(n)

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