22. Generate Parentheses

MediumBacktrackingBacktracking with running open/close countsConstrained string construction

Generate Parentheses

Given n pairs of parentheses, generate all combinations of well-formed (valid) parentheses strings of length 2n. Every open bracket must be matched by a later close bracket.

Open official problem prompt ↗

In plain English

Produce every balanced parentheses string that uses exactly n opening and n closing brackets.

Picture it like this

Stacking and unstacking plates: you can only place a plate down (open) if you have plates left, and you can only remove one (close) if the stack is non-empty; every valid sequence of moves is one answer.

Example

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Why: These are exactly the 5 balanced strings using 3 '(' and 3 ')'; the count is the 3rd Catalan number, C(3) = 5.

Constraints

1 <= n <= 8

Pattern lesson

See the pattern, then code

Constrained string construction

↗

Backtracking

Generate every valid combination, permutation, partition, or configuration.. Add '(' whenever we still have opens left (open < n). Add ')' only when it would not leave more closes than opens (close < open). Enforcing these two rules at every step guarantees every generated string is valid, so no post-filtering is needed.

New words, made simpleKnow these before the algorithm

Well-formed / balanced: Every ')' has a matching earlier '(', and counts of each are equal by the end.
Open count: How many '(' have been placed so far; capped at n.
Catalan number: The count of valid sequences for n pairs, C(n); C(3) = 5, C(4) = 14.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Generate all 2^(2n) strings then filter

Wastes enormous effort building and discarding invalid strings; impractical even for modest n.

Produce every string of ( and ) of length 2n and keep the balanced ones.

Time O(2^(2n) * n)Space O(n)

Best choiceBacktracking with count pruning

Never builds an invalid prefix, so every leaf is a valid answer; the standard optimal approach.

Grow the string one bracket at a time, only adding '(' while open < n and ')' while close < open.

Time O(4^n / sqrt(n))Space O(n)

The rule we keep true

Invariant

Throughout recursion the prefix in path is a valid partial sequence: close_count <= open_count <= n at all times.

Why this is correct

Reasoning

The two guards preserve the invariant that closes never exceed opens and opens never exceed n. Any string reaching length 2n under these rules is fully balanced by construction, and because both legal moves are always attempted, no valid arrangement is skipped.

The algorithm in three movesSay these aloud before coding

1Stop when the string length reaches 2n and record it

open=1 -> '('

2If open < n, append '(' and recurse

open=2 -> '(('

3If close < open, append ')' and recurse; pop after each branch

open=3 -> '(((' then close x3 -> '((()))'

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readopen<n three times

2 · AskCan we add '('?

3 · Update statepath='((('

4 · Resultopen=3=n, opens exhausted

Key takeaway

The leftmost branch opens three times then closes three times to form ((()))

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 7-9Completion base case
When the path has 2n characters it is a complete valid string; join and record it.
2
Lines 10-13Open bracket rule
Add '(' only while fewer than n opens have been used, then recurse and restore.
3
Lines 14-17Close bracket rule
Add ')' only when there are unmatched opens (close < open), guaranteeing balance.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

n = 1 -> single answer "()"
Largest n = 8 -> 1430 (C(8)) strings
Never produces strings starting with ')' because close < open fails at the root

Common beginner mistakes

Allowing ')' when close == open, producing invalid strings like ')('
Bounding by total length only without the open/close guards, forcing a filter step
Comparing open + close to n instead of open to n and close to open

Check your understanding

Why does the condition for adding ')' compare close_count to open_count rather than to n?

PyPython 3 · solution.py

Optimal

1class Solution:2    def generateParenthesis(self, n: int) -> list[str]:3        res: list[str] = []4        path: list[str] = []56        def backtrack(open_count: int, close_count: int) -> None:7            if len(path) == 2 * n:8                res.append(''.join(path))9                return10            if open_count < n:11                path.append('(')12                backtrack(open_count + 1, close_count)13                path.pop()14            if close_count < open_count:15                path.append(')')16                backtrack(open_count, close_count + 1)17                path.pop()1819        backtrack(0, 0)20        return res

Time complexityO(4^n / sqrt(n))Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

MetaAmazonGoogleApple

Generate Parentheses

Generate Parentheses

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Backtracking