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
def generateParenthesis(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 it fails at scale: at n = 8 that’s 65,536 candidates of length 16. Only about 2% are valid, and that fraction shrinks as n grows, so almost all the work is wasted. Generating only valid strings is the point of the exercise.
Approach 2 — Backtracking on the validity invariant
A partial string can be extended to a valid one iff opens <= n and closes <= opens. Instead of validating after the fact, enforce the invariant while building: add ( if opens < n, and ) if closes < opens. Every path in this pruned tree ends in a valid string. This is backtracking: depth-first construction of partial solutions with undo, abandoning branches that cannot lead to an answer. Here the invalid branches are never entered at all.
def generateParenthesis(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, giving path ( (opens 1). From there both moves are legal. Opening again gives ((, which can only close twice to (()). Closing instead gives (), which must open (closes are not < opens), giving ()( and then ()(). The recursion tree has exactly 2 leaves, ["(())", "()()"], and never touches the other 14 strings of length 4.
flowchart TD
R["'' (0,0)"] --> A["( (1,0)"]
A --> B["(( (2,0)"]
A --> C["() (1,1)"]
B --> D["(() (2,1)"]
D --> E["(()) — leaf"]
C --> F["()( (2,1)"]
F --> G["()() — leaf"]
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 is O(n) for the path and recursion depth, which serves as the stack in this stack-pattern problem.
Approach 3 — Dynamic programming on the first closure
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: solve each subproblem once and combine the stored results.
def generateParenthesis(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 cost backtracking does not 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 doubles as the stack.