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 - LeetCode Solution

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.

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

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 '('. This pruning ensures that partial strings are always valid prefixes, eliminating invalid branches early and reducing the search space from 2^(2n) to the nth Catalan number, which is much smaller.

Optimal Approach

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.

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

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

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
  public List<String> generateParenthesis(int n) {
      List<String> res = new ArrayList<>();
      StringBuilder stack = new StringBuilder();
8
      backtrack(n, 0, 0, stack, res);
      return res;
  }
12
  private void backtrack(int n, int openCount, int closedCount, StringBuilder stack, List<String> res) {
      if (openCount == n && closedCount == n) {
          res.add(stack.toString());
          return;
      }
18
      if (openCount < n) {
          stack.append('(');
          backtrack(n, openCount + 1, closedCount, stack, res);
          stack.deleteCharAt(stack.length() - 1);
      }
24
      if (closedCount < openCount) {
          stack.append(')');
          backtrack(n, openCount, closedCount + 1, stack, res);
          stack.deleteCharAt(stack.length() - 1);
      }
  }
31}

1#include <string>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8    vector<string> generateParenthesis(int n) {
9        vector<string> res;
10        string stack;
11        backtrack(n, 0, 0, stack, res);
12        return res;
13    }
14
15private:
16    void backtrack(int n, int openCount, int closedCount, string& stack, vector<string>& res) {
17        if (openCount == n && closedCount == n) {
18            res.push_back(stack);
19            return;
20        }
21
22        if (openCount < n) {
23            stack.push_back('(');
24            backtrack(n, openCount + 1, closedCount, stack, res);
25            stack.pop_back();
26        }
27
28        if (closedCount < openCount) {
29            stack.push_back(')');
30            backtrack(n, openCount, closedCount + 1, stack, res);
31            stack.pop_back();
32        }
33    }
34};

1var generateParenthesis = function(n) {
  const res = [];
  const stack = [];
4
  function backtrack(openCount, closedCount) {
      if (openCount === n && closedCount === n) {
          res.push(stack.join(''));
          return;
      }
10
      if (openCount < n) {
          stack.push('(');
          backtrack(openCount + 1, closedCount);
          stack.pop();
      }
16
      if (closedCount < openCount) {
          stack.push(')');
          backtrack(openCount, closedCount + 1);
          stack.pop();
      }
  }
23
  backtrack(0, 0);
  return res;
26};

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.

Line 16 Critical

if closed_count < open_count:

Check if a closing parenthesis can be added without invalidating the string.

A closing parenthesis can only be added if closed_count is less than open_count, preserving the invariant that the partial string is valid.

Line 6 Core

def backtrack(open_count, closed_count):

Define the recursive backtracking function with counts of open and closed parentheses.

Tracking open and closed counts as parameters encodes the current state of the partial string, enabling constraint checks to prune invalid paths.

Line 11 Core

if open_count < n:

Check if more opening parentheses can be added.

Adding '(' is only valid if the count of '(' is less than n, ensuring the final string has exactly n pairs.

Line 13 Core

backtrack(open_count + 1, closed_count)

Recursively call backtrack with incremented open_count.

This explores all valid continuations after adding an opening parenthesis, advancing the state.

Line 18 Core

backtrack(open_count, closed_count + 1)

Recursively call backtrack with incremented closed_count.

This explores all valid continuations after adding a closing parenthesis, advancing the state.

Line 3 Core

stack = []

Initialize a stack list to build partial parentheses strings.

Using a mutable list as a stack allows efficient appending and popping of characters during backtracking, enabling state restoration without creating new strings at each recursion.

Line 8 Core

res.append("".join(stack))

Append the current valid combination to the results as a string.

Joining the stack into a string captures the current valid parentheses sequence for storage, preserving it before backtracking.

Line 12 Core

stack.append("(")

Add an opening parenthesis to the stack.

Appending '(' extends the partial string while maintaining validity, enabling exploration of deeper states.

Line 17 Core

stack.append(")")

Add a closing parenthesis to the stack.

Appending ')' extends the partial string while maintaining validity, enabling exploration of deeper states.

Line 21 Core

backtrack(0, 0)

Start the backtracking process with zero open and closed parentheses.

This initializes the recursive exploration from an empty string, setting the base state.

Line 9 Standard

return

Return from recursion after adding a complete combination.

This terminates the current recursion branch, preventing further exploration beyond a complete valid string.

Line 22 Standard

return res

Return the list of all valid parentheses combinations.

After exploring all valid states, this returns the accumulated results to the caller.

Line 4 Standard

res = []

Initialize the result list to store all valid parentheses combinations.

This list accumulates all complete valid strings found during the recursive exploration.

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?

Because adding a closing parenthesis when there are not enough opening parentheses would create an invalid prefix that cannot be completed into a valid parentheses string. Ensuring closed_count < open_count maintains the invariant that the partial string is always a valid prefix.

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`

1	`import java.util.ArrayList;`
2	`import java.util.List;`
3
4	`class Solution {`
5	`public List<String> generateParenthesis(int n) {`
6	`List<String> res = new ArrayList<>();`
7	`StringBuilder stack = new StringBuilder();`
8
9	`backtrack(n, 0, 0, stack, res);`
10	`return res;`
11	`}`
12
13	`private void backtrack(int n, int openCount, int closedCount, StringBuilder stack, List<String> res) {`
14	`if (openCount == n && closedCount == n) {`
15	`res.add(stack.toString());`
16	`return;`
17	`}`
18
19	`if (openCount < n) {`
20	`stack.append('(');`
21	`backtrack(n, openCount + 1, closedCount, stack, res);`
22	`stack.deleteCharAt(stack.length() - 1);`
23	`}`
24
25	`if (closedCount < openCount) {`
26	`stack.append(')');`
27	`backtrack(n, openCount, closedCount + 1, stack, res);`
28	`stack.deleteCharAt(stack.length() - 1);`
29	`}`
30	`}`
31	`}`

1	`#include <string>`
2	`#include <vector>`
3
4	`using namespace std;`
5
6	`class Solution {`
7	`public:`
8	`vector<string> generateParenthesis(int n) {`
9	`vector<string> res;`
10	`string stack;`
11	`backtrack(n, 0, 0, stack, res);`
12	`return res;`
13	`}`
14
15	`private:`
16	`void backtrack(int n, int openCount, int closedCount, string& stack, vector<string>& res) {`
17	`if (openCount == n && closedCount == n) {`
18	`res.push_back(stack);`
19	`return;`
20	`}`
21
22	`if (openCount < n) {`
23	`stack.push_back('(');`
24	`backtrack(n, openCount + 1, closedCount, stack, res);`
25	`stack.pop_back();`
26	`}`
27
28	`if (closedCount < openCount) {`
29	`stack.push_back(')');`
30	`backtrack(n, openCount, closedCount + 1, stack, res);`
31	`stack.pop_back();`
32	`}`
33	`}`
34	`};`

1	`var generateParenthesis = function(n) {`
2	`const res = [];`
3	`const stack = [];`
4
5	`function backtrack(openCount, closedCount) {`
6	`if (openCount === n && closedCount === n) {`
7	`res.push(stack.join(''));`
8	`return;`
9	`}`
10
11	`if (openCount < n) {`
12	`stack.push('(');`
13	`backtrack(openCount + 1, closedCount);`
14	`stack.pop();`
15	`}`
16
17	`if (closedCount < openCount) {`
18	`stack.push(')');`
19	`backtrack(openCount, closedCount + 1);`
20	`stack.pop();`
21	`}`
22	`}`
23
24	`backtrack(0, 0);`
25	`return res;`
26	`};`

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`