Generate Parentheses

Problem

Given an integer n, produce every distinct string of n opening and n closing parentheses that is well-formed — reading left to right, the count of ) never exceeds the count of (, and the counts are equal at the end. Return the strings in any order.

Examples

• n = 1 → ["()"] — only one balanced string of length 2.
• n = 2 → ["(())", "()()"] — nest or concatenate.
• n = 3 → ["((()))", "(()())", "(())()", "()(())", "()()()"] — the 5 balanced strings of length 6 (5 is the 3rd Catalan number).

Constraints

• 1 <= n <= 8

The output itself is exponential (Catalan-number many strings, ~1430 for n = 8), so the goal is to generate only valid strings — never enumerate all 2^(2n) candidates and filter.

Think about it first

TL;DR

Backtracking with open/close counters, emitting only valid strings — O(4^n / √n) time (proportional to the Catalan-sized output), O(n) extra space beyond the output.

Approach 1 — Brute force

Generate all 2^(2n) strings of ( and ) and keep the valid ones, checking validity with a running counter (a degenerate stack: the stack would only ever hold (, so its height is enough).

from itertools import product


class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        def valid(cand: tuple[str, ...]) -> bool:
            height = 0
            for ch in cand:
                height += 1 if ch == "(" else -1
                if height < 0:
                    return False
            return height == 0

        out: list[str] = []
        for cand in product("()", repeat=2 * n):
            if valid(cand):
                out.append("".join(cand))
        return out

Complexity: O(2^(2n) · n) time, O(n) working space.

Why the constraints kill it: at n = 8 that’s 65,536 candidates of length 16 — survivable, but only ~2% of them are valid; the wasted 98% grows without bound and the approach dies immediately past the constraint. Generating only valid strings is the point of the exercise.

Approach 2 — Backtracking on the validity invariant

The insight: a partial string can be extended to a valid one iff opens <= n and closes <= opens. So instead of validating after the fact, enforce the invariant while building: at each step you may add ( if opens < n, and ) if closes < opens. Every path in this pruned tree ends in a valid string — zero waste. This is backtracking: depth-first construction of partial solutions with undo, abandoning branches the moment they can’t lead to an answer (here, invalid branches are never even entered).

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        res: list[str] = []
        path: list[str] = []

        def backtrack(opens: int, closes: int) -> None:
            if len(path) == 2 * n:
                res.append("".join(path))
                return
            if opens < n:
                path.append("(")
                backtrack(opens + 1, closes)
                path.pop()                    # undo before trying ')'
            if closes < opens:
                path.append(")")
                backtrack(opens, closes + 1)
                path.pop()

        backtrack(0, 0)
        return res

Walkthrough for n = 2: the root must open — path ( (opens 1). From there both moves are legal: opening again gives ((, which can only close twice → (()); closing instead gives (), which must open (closes are not < opens), giving ()( and then ()(). The recursion tree has exactly 2 leaves, ["(())", "()()"] — it never touched the other 14 strings of length 4.

Complexity: the number of valid strings is the nth Catalan number C(2n, n)/(n+1) — the count of balanced bracketings — which grows as Θ(4^n / n^1.5); total work is O(4^n / √n) counting the O(n) copy per leaf. Extra space O(n) for the path and recursion depth (which acts as the stack in this “stack pattern” problem).

Approach 3 — Dynamic programming on the first closure

The insight: every valid string decomposes uniquely as "(" + A + ")" + B, where A is the (valid) content inside the first (’s matching ), and B is the (valid) remainder. If A uses i pairs, B uses n − 1 − i. Build answers bottom-up from smaller n — classic dynamic programming: solve each subproblem once and combine stored results.

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        dp: list[list[str]] = [[""]]          # dp[0]: one empty string
        for k in range(1, n + 1):
            cur: list[str] = []
            for i in range(k):                # pairs inside the first group
                for inner in dp[i]:
                    for rest in dp[k - 1 - i]:
                        cur.append("(" + inner + ")" + rest)
            dp.append(cur)
        return dp[n]

Walkthrough for n = 2: dp[1] is built from i = 0: "(" + "" + ")" + "" → ["()"]. dp[2] takes i = 0: "()" ++ rest ∈ dp[1] → "()()", and i = 1: "(" + "()" + ")" → "(())". Result ["()()", "(())"] — the same 2 strings.

Complexity: output-linear like backtracking, O(4^n / √n) time; O(4^n / √n) space because all smaller levels are retained (a real cost backtracking doesn’t pay).

Common pitfalls

• Checking closes < n instead of closes < opens — that generates invalid strings like ")("; the closing move is legal only against an unmatched (.
• Forgetting to undo (path.pop()) when using a shared mutable buffer — siblings inherit a corrupted prefix. Passing immutable strings down avoids this at some copying cost.
• Deduplicating with a set — unnecessary; both the backtracking tree and the first-closure decomposition produce each string exactly once.
• Calling the complexity O(2^n) or O(n!) — the tight answer is the Catalan asymptotic Θ(4^n / n^1.5); interviewers often probe this.

Pattern takeaway

When asked to enumerate all structures satisfying a prefix-checkable invariant, push the validity check into the generator: recurse only on extensions that keep the invariant, and every leaf is an answer. The open/close counter is a stack reduced to its height — the same balance invariant behind Valid Parentheses — and the backtracking recursion is itself the stack pattern in disguise.