How do you solve Generate Parentheses?

Use a recursive backtracking function that tracks the counts of open and closed parentheses added so far. At each step, if open_count < n, add '(' and recurse. If closed_count < open_count, add ')' and recurse. When both counts reach n, add the constructed string to the result list. This approach generates all valid combinations efficiently.

What pattern does Generate Parentheses use?

The Pattern: Backtracking (State Restoration) The Heuristic: For generating all valid combinations under constraints, incrementally build partial solutions and prune invalid states early by enforcing constraints at each step, restoring state after recursion to explore alternative branches.

Generate Parentheses — Backtracking

Q: What is the time complexity of Generate Parentheses?

O(4^n / sqrt(n)). The number of valid parentheses sequences corresponds to the nth Catalan number, which grows asymptotically as O(4^n / (n^(3/2))). The backtracking algorithm generates all valid sequences without exploring invalid ones, so its time complexity matches the number of valid outputs.

Q: What pattern does Generate Parentheses use?

The Pattern: Backtracking (State Restoration) The Heuristic: For generating all valid combinations under constraints, incrementally build partial solutions and prune invalid states early by enforcing constraints at each step, restoring state after recursion to explore alternative branches.

Problem

Given an integer n, return all combinations of well-formed parentheses consisting of n pairs of parentheses.

1 ≤ n ≤ 8

Example

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

The brute-force approach would generate all possible strings of length 6 (2*n) consisting of '(' and ')' and then filter those that are valid. This is inefficient because the number of such strings is 2^(2n), which grows exponentially. Instead, the algorithm uses backtracking to build valid strings incrementally, pruning invalid partial strings early. Starting with an empty string and zero counts for open and closed parentheses, the algorithm adds '(' if the count of open parentheses is less than n, and adds ')' if the count of closed parentheses is less than the count of open parentheses. This ensures that at every step, the partial string remains valid. When both counts reach n, a complete valid combination is formed and added to the results. For example, with n=3, the algorithm explores adding '(' three times, then adds ')' three times, backtracking to explore all valid permutations. This pruning drastically reduces the search space compared to brute force.

Approach

Straightforward Solution

A brute-force approach would generate all 2^(2n) strings of '(' and ')' of length 2n and then check each for validity. This is computationally infeasible for larger n due to exponential explosion.

Core Observation

The problem requires generating all valid sequences of parentheses, which are strings of length 2n with balanced opening and closing parentheses. The key property is that at any prefix of the string, the number of '(' must be at least the number of ')'.

Path to Optimal

Preview

The key insight is to build the string incrementally using backtracking, only adding '(' when the count of '(' is less than n, and adding ')' only when the count of ')' is less than the count of '('…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a recursive backtracking function that tracks the counts of open and closed parentheses added so far. At each step, if open_count < n, add '(' and recurse…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(4^n / sqrt(n))

The number of valid parentheses sequences corresponds to the nth Catalan number, which grows asymptotically as O(4^n / (n^(3/2))). The backtracking algorithm generates all valid sequences without exploring invalid ones, so its time complexity matches the number of valid outputs.

Space

O(n)

The recursion stack and the temporary string builder (stack) use O(n) space, proportional to the maximum depth of recursion and length of the current partial string. The output list is not counted as auxiliary space.

Solution

Python

1class Solution:
  def generateParenthesis(self, n: int) -> list[str]:
      stack = []
      res = []
5
      def backtrack(open_count, closed_count):
          if open_count == closed_count == n:
              res.append("".join(stack))
              return
10
          if open_count < n:
              stack.append("(")
              backtrack(open_count + 1, closed_count)
              stack.pop()
          
          if closed_count < open_count:
              stack.append(")")
              backtrack(open_count, closed_count + 1)
              stack.pop()
20
      backtrack(0, 0)
      return res

Step-by-Step Solution

1

Build Valid Parentheses Combinations via Recursive Backtracking

3stack = []
4res = []
6def backtrack(open_count, closed_count):
7    if open_count == closed_count == n:
8        res.append("".join(stack))
9        return
11    if open_count < n:
12        stack.append("(")
13        backtrack(open_count + 1, closed_count)
14        stack.pop()
16    if closed_count < open_count:
17        stack.append(")")
18        backtrack(open_count, closed_count + 1)
19        stack.pop()
21backtrack(0, 0)
22return res

Objective

To recursively construct all valid parentheses strings by adding '(' or ')' only when constraints allow, ensuring partial strings remain valid.

Key Insight

The backtracking function uses two counters to track how many '(' and ')' have been added. It only adds '(' if the count is less than n, and only adds ')' if it won't invalidate the string (i.e., closed_count < open_count). This pruning avoids generating invalid strings and reduces the search space drastically. The stack list acts as a mutable builder for the current string, and popping after recursion restores state for exploring alternative branches.

Interview Quick-Check

Core Logic

Backtracking incrementally builds valid strings by enforcing constraints on open and closed parentheses counts, pruning invalid partial solutions early.

State & Boundaries

The recursion terminates when both open and closed counts reach n, indicating a complete valid combination.

Common Pitfalls & Bugs

Forgetting to pop from the stack after recursive calls leads to incorrect state sharing and invalid results.

Complexity

The algorithm generates all valid sequences, which are counted by the Catalan number, ensuring efficient enumeration without redundant work.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 14 Critical

stack.pop()

Remove the last added character to restore state after recursion.

Popping restores the stack to its previous state, allowing exploration of alternative branches without side effects.

Line 19 Critical

stack.pop()

Remove the last added character to restore state after recursion.

Popping restores the stack to its previous state, allowing exploration of alternative branches without side effects.

Line 7 Critical

if open_count == closed_count == n:

Check if the current string is complete with n pairs of parentheses.

When both open and closed counts reach n, the partial string is a valid complete combination and should be added to the results.

Full line-by-line criticality + rationale for all 16 lines available on Pro.

Test Your Understanding

Why does the algorithm only add a closing parenthesis when the count of closing parentheses is less than the count of opening parentheses?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Generate Parentheses from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Generate Parentheses drill

or drill a free problem

1	`class Solution:`
2	`def generateParenthesis(self, n: int) -> list[str]:`
3	`stack = []`
4	`res = []`
5
6	`def backtrack(open_count, closed_count):`
7	`if open_count == closed_count == n:`
8	`res.append("".join(stack))`
9	`return`
10
11	`if open_count < n:`
12	`stack.append("(")`
13	`backtrack(open_count + 1, closed_count)`
14	`stack.pop()`
15
16	`if closed_count < open_count:`
17	`stack.append(")")`
18	`backtrack(open_count, closed_count + 1)`
19	`stack.pop()`
20
21	`backtrack(0, 0)`
22	`return res`

3	`stack = []`
4	`res = []`
6	`def backtrack(open_count, closed_count):`
7	`if open_count == closed_count == n:`
8	`res.append("".join(stack))`
9	`return`
11	`if open_count < n:`
12	`stack.append("(")`
13	`backtrack(open_count + 1, closed_count)`
14	`stack.pop()`
16	`if closed_count < open_count:`
17	`stack.append(")")`
18	`backtrack(open_count, closed_count + 1)`
19	`stack.pop()`
21	`backtrack(0, 0)`
22	`return res`