Generate Parentheses

Given n pairs, list every well-formed combination — grow one valid prefix at a time, opening while opens remain and closing only while closes trail opens.

The memory hook

Open while you still have opens to spend, close only while closes trail opens — every answer is one root-to-leaf path through those two gates.

MediumBacktracking · open/close countersO(4ⁿ/√n) timeO(n) space

Two counters, two gates, one prefix

intuition

A partial string is buildable into a valid answer exactly when it never dips negative — closes never exceed opens, and opens never exceed n. So the whole search state is just the pair (opens used, closes used), and each step faces at most two legal moves. The recursion walks every legal prefix depth-first; leaves at length 2n are precisely the answers.

1Grow one prefixThe current path holds a valid prefix of length open + close. Position open + close is the only decision this frame makes; everything after it stays empty.

2Pass the two gatesAppend ( only if open < n — opens remain to spend. Append ) only if close < open — a matching open exists. Failing a gate prunes that whole subtree, which is why no invalid string is ever built.

3Record at full length, undo on returnAt length 2n both counters are exhausted, so the path is a complete answer — copy it out. Then pop and let the sibling branch start from identical state.

The one sentence to remember: The pair (opens used, closes used) with closes ≤ opens ≤ n is the entire search state, and the two gate checks admit exactly the prefixes of well-formed strings.

Watch the prefix grow and shrink

playable trace

Step through n = 3. Each frame appends one bracket through a gate or undoes it; the five lime frames are the moments the path reaches length 6 and a copy is recorded. Try n = 2 to see nesting versus chaining side by side.

Playable trace · backtracking · open/close counters

Frames are generated from the same logic as the code below.

Presets

Current event

Ready — press Play

Found

0 / 5

Completions

The path starts empty with 3 opens and 0 closes spent. Press Play.

empty slot current choice in path just undone complete

0 / 0 speed 650ms

Open, close, undo

the solution

Python · backtracking · open/close counters

class Solution:
    def generateParenthesis(self, n: int):
        res = []
        def dfs(path, open, close):
            if len(path) == 2 * n:  # both counters spent: one full answer
                res.append(''.join(path))  # join now: path keeps mutating
                return
            if open < n:  # gate 1: opens remain to spend
                path.append('(')
                dfs(path, open + 1, close)
                path.pop()  # undo: free the slot for the sibling
            if close < open:  # gate 2: a matching open exists
                path.append(')')
                dfs(path, open, close + 1)
                path.pop()  # undo: restore state for the caller
        dfs([], 0, 0)
        return res

The displayed Python and the trace above use the same logic: full-length copy, the two gate checks, and a paired pop after each recursive call.

Complete at full lengthif len(path) == 2 * nThe only place answers are recorded. Both counters are exhausted here, so the path holds n opens and n closes in a valid order — exactly one answer per leaf.

Open gateif open < nAn ( is legal only while opens remain. Once open reaches n, that entire subtree is closed — every continuation from here is closes only.

Close gateif close < openA ) is legal only while an unmatched ( exists. This single check is what keeps every prefix non-negative and prunes all invalid strings before they are built.

Why is every valid string listed exactly once? Induction on the prefix: each valid string's prefixes all satisfy close ≤ open ≤ n, so the search follows its exact decision path to a leaf; each invalid prefix fails a gate and is never extended. Distinct first-differing positions give disjoint subtrees.

TimeO(4ⁿ/√n)The output itself has Catalan(n) ≈ 4ⁿ/(n√n) strings, each of length 2n — printing them dominates. Internal nodes are proportional to the leaves, so search adds only a constant factor.

SpaceO(n)Path plus recursion depth 2n besides the output, which itself holds Catalan(n) strings of length 2n.

Two quick mental checks

make it stick

n = 3

→ 5 combinations

((())), (()()), (())(), ()(()), ()()() — the first is pure nesting, the last pure chaining, and the middle three mix. The trace's five lime frames arrive in exactly this order.

n = 1 → ["()"] · n = 2 → ["(())","()()"]

→ nesting vs chaining

n = 2 already shows both shapes: nest the second pair inside or chain it after. Every larger n just interleaves these two moves under the same gates.

What to say out loud

I track opens and closes used and grow one prefix depth-first: I append an open parenthesis while opens remain, a close parenthesis only while closes trail opens, and I record a copy when the path reaches length two n. The gates admit exactly the valid prefixes, so each complete string is generated once and nothing invalid is ever built.