Problem editorial

Generate Parentheses

MediumBacktracking PatternsStringDynamic ProgrammingBacktracking

Editorial

Core insight

Generate Parentheses · Backtracking Patterns

Core Insight for Generate Parentheses

The key insight that optimizes the brute force approach is that we can enforce validity during the generation process rather than checking it at the end.

To generate a valid parenthesis string, two critical constraints (invariants) must be maintained throughout the recursion:

Open Constraint: We can only add an opening parenthesis ( if we have not yet used all n opening parentheses.
Close Constraint: We can only add a closing parenthesis ) if the count of closing parentheses used so far is strictly less than the count of opening parentheses used. This ensures we never have a "dangling" closing bracket (e.g., ()) is invalid because the second ) has no matching ().

Visual Description: Imagine the algorithm as traversing a binary tree. The root represents an empty string.

At Node A (string (), we have two choices: go left to add ( or right to add ).
If we have used n open brackets, the "left" branch is pruned (does not exist).
If the number of closed brackets equals the number of open brackets, the "right" branch is pruned.
The algorithm only visits nodes representing valid prefixes, significantly reducing the search space compared to the full binary tree of the brute force approach.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 22: Generate Parentheses Solution & Explanation

Problem Overview

TL;DR: We use backtracking to build strings character by character, maintaining a count of open and closed parentheses to ensure every generated string is valid by construction.

The problem asks us to generate all possible well-formed parenthesis combinations given n pairs. This means we must construct every unique string containing exactly n opening brackets ( and n closing brackets ) such that every opening bracket is properly closed in the correct order.

This is a classic combinatorial problem often referred to as "LeetCode 22" or "Generate Parentheses" in interview contexts. It serves as a foundational exercise for understanding state-space trees and pruning invalid paths.

Brute Force Approach for Generate Parentheses

The naive approach attempts to generate every possible string of length 2n consisting of ( and ) characters, and then validates each string.

Naive Algorithm:

Generate all $2^{2n}$ sequences of length 2n.
Iterate through the list of sequences.
For each sequence, run a validation function (using a counter or stack) to check if it is well-formed.
If valid, add to the result list.

Pseudo-code:

text

function generate(current_string):
    if length of current_string == 2 * n:
        if isValid(current_string):
            add to results
        return

    generate(current_string + "(")
    generate(current_string + ")")

Why this fails: The time complexity is $O(n \cdot 2^{2n})$ . For $n=3$ , this is manageable. However, the growth is exponential. The vast majority of generated strings (e.g., ))))(() are invalid. We waste significant computational cycles building and checking strings that could have been identified as invalid much earlier in the construction process.

Algorithm Strategy: Backtracking Patterns

We define a recursive function backtrack that accepts the current string state and counters for the parentheses used.

State Variables:

current_string: The string built so far.
open_count: The number of ( used.
close_count: The number of ) used.
n: The total pairs required.

Logic:

Base Case: If the length of current_string is 2 * n, we have a complete, valid combination. Add it to the results and return.
Recursive Step (Open): If open_count < n, append ( and recurse with open_count + 1.
Recursive Step (Close): If close_count < open_count, append ) and recurse with close_count + 1.

By strictly following the condition close_count < open_count, we guarantee that at any point in the recursion, the prefix is valid, and we never generate a malformed string.

Execution Flow

Let's trace the execution for n = 2. Target length is 4.

Start: str="", open=0, close=0
Step 1: open < 2, add (.
- State: str="(", open=1, close=0
Step 2:
- Option A: open < 2, add (.
  - State: str="((", open=2, close=0
  - Next: open is not < 2. Only option is close.
  - Add ) -> str="(()", open=2, close=1
  - Add ) -> str="(())", open=2, close=2. Base Case Reached. Add to result.
- Option B: close < open (0 < 1), add ).
  - State: str="()", open=1, close=1
  - Next: close is not < open (1 is not < 1). Only option is open.
  - Add ( -> str="()(", open=2, close=1
  - Add ) -> str="()()", open=2, close=2. Base Case Reached. Add to result.

Final Result: ["(())", "()()"]

Proof of Correctness

The algorithm is correct because it exhaustively explores all valid decision paths while maintaining the property of well-formedness.

Validity: By ensuring close_count never exceeds open_count, we prevent prefixes like ()). By ensuring open_count never exceeds n, we ensure the correct count.
Completeness: The algorithm explores every possible valid addition at every step. Since we branch for both ( and ) whenever valid, no valid combination is omitted.

Pattern Reuse Notes

The logic used in LeetCode 22 applies to other problems requiring the generation of valid structural combinations:

LeetCode 301: Remove Invalid Parentheses: Uses similar logic to explore states, removing parentheses to reach a valid state.
Valid Parenthesis String (checking): The counter logic (open vs close) is the standard greedy approach for validating parenthesis strings.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 22

cpp

1class Solution {
2public:
3    vector<string> generateParenthesis(int n) {
4        vector<string> result;
5        string current;
6        backtrack(result, current, 0, 0, n);
7        return result;
8    }
9
10private:
11    void backtrack(vector<string>& result, string& current, int open, int close, int n) {
12        // Base case: if the string length is 2*n, we have a valid combination
13        if (current.length() == n * 2) {
14            result.push_back(current);
15            return;
16        }
17
18        // Decision 1: Add open parenthesis if we haven't used all of them
19        if (open < n) {
20            current.push_back('(');
21            backtrack(result, current, open + 1, close, n);
22            current.pop_back(); // Backtrack
23        }
24
25        // Decision 2: Add close parenthesis if valid (count < open count)
26        if (close < open) {
27            current.push_back(')');
28            backtrack(result, current, open, close + 1, n);
29            current.pop_back(); // Backtrack
30        }
31    }
32};

Java Solution for LeetCode 22

java

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    public List<String> generateParenthesis(int n) {
6        List<String> result = new ArrayList<>();
7        // Use StringBuilder for efficient mutation during backtracking
8        backtrack(result, new StringBuilder(), 0, 0, n);
9        return result;
10    }
11
12    private void backtrack(List<String> result, StringBuilder current, int open, int close, int n) {
13        // Base case: Valid string formed
14        if (current.length() == n * 2) {
15            result.add(current.toString());
16            return;
17        }
18
19        // Decision 1: Add open parenthesis
20        if (open < n) {
21            current.append('(');
22            backtrack(result, current, open + 1, close, n);
23            current.deleteCharAt(current.length() - 1); // Backtrack
24        }
25
26        // Decision 2: Add close parenthesis
27        if (close < open) {
28            current.append(')');
29            backtrack(result, current, open, close + 1, n);
30            current.deleteCharAt(current.length() - 1); // Backtrack
31        }
32    }
33}

Python Solution for LeetCode 22

python

1class Solution:
2    def generateParenthesis(self, n: int) -> List[str]:
3        result = []
4        
5        def backtrack(current_string, open_count, close_count):
6            # Base case: if string is complete
7            if len(current_string) == 2 * n:
8                result.append(current_string)
9                return
10
11            # Decision 1: Add open parenthesis
12            if open_count < n:
13                backtrack(current_string + "(", open_count + 1, close_count)
14
15            # Decision 2: Add close parenthesis
16            if close_count < open_count:
17                backtrack(current_string + ")", open_count, close_count + 1)
18        
19        # Start the recursion
20        backtrack("", 0, 0)
21        return result

AI Coach Insight

For Generate Parentheses, focus on explaining why the structure works, not just naming Backtracking Patterns.

Complexity Analysis

Time Complexity: $O(\frac{4^n}{\sqrt{n}})$ The number of valid parenthesis strings with $n$ pairs is the $n$ -th Catalan number, which is given by $\frac{1}{n+1}\binom{2n}{n}$ . Asymptotically, this grows as $\frac{4^n}{n^{1.5}}$ . Since we construct each string of length $2n$ , the total work is roughly $O(n \cdot \text{Catalan}(n))$ , which simplifies to $O(\frac{4^n}{\sqrt{n}})$ . While exponential, this is the optimal complexity because we must generate every valid string.

Space Complexity: $O(n)$ The space complexity is determined by the maximum depth of the recursion stack. Since we generate strings of length $2n$ , the recursion depth is $2n$ , resulting in linear space complexity $O(n)$ . Note that this excludes the space required to store the output list.

Related Patterns

Pattern: Backtracking Patterns
Subpattern: Backtracking - Parentheses Generation

This problem fits the Backtracking pattern because we are constructing a solution incrementally. As we build the string, we make a decision (add ( or add )), recurse to the next state, and potentially backtrack. By adhering to specific constraints at each step, we "prune" the recursion tree, ensuring we never descend into a branch that leads to an invalid string.

Common Mistakes & FAQ

Q: Why does my solution get a Time Limit Exceeded (TLE)?
- Mistake: Implementing the brute force approach (generating all permutations) and checking validity afterwards.
- Gap: Failing to recognize that we can prune invalid branches immediately.
- Consequence: The algorithm processes exponentially more states than necessary ( $2^{2n}$ vs Catalan number).
Q: Why are my output strings malformed (e.g., ()))?
- Mistake: Checking if close < n instead of if close < open when adding a closing bracket.
- Gap: Misunderstanding the invariant. A closing bracket is only valid if there is an unmatched opening bracket preceding it.
- Consequence: The algorithm generates strings that balance the total count but violate the structural order.
Q: Why is my recursion infinite or crashing?
- Mistake: Incorrect base case or state updates (e.g., passing open instead of open + 1).
- Gap: Basic recursion implementation errors.
- Consequence: Stack overflow error.
Q: Why do I have duplicate strings in the output?
- Mistake: This usually happens if the logic allows overlapping branches, though strictly following the open vs close logic prevents this naturally.
- Gap: In more complex backtracking, duplicates occur if the same state is reached via different paths.
- Consequence: Inefficient and incorrect result size.

Practise Generate Parentheses and the problems around it

Generate Parentheses is a Backtracking Patterns problem, in the Parentheses Generation subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

Generate Parentheses · Backtracking Patterns

Core Insight for Generate Parentheses

The key insight that optimizes the brute force approach is that we can enforce validity during the generation process rather than checking it at the end.

To generate a valid parenthesis string, two critical constraints (invariants) must be maintained throughout the recursion:

Open Constraint: We can only add an opening parenthesis ( if we have not yet used all n opening parentheses.
Close Constraint: We can only add a closing parenthesis ) if the count of closing parentheses used so far is strictly less than the count of opening parentheses used. This ensures we never have a "dangling" closing bracket (e.g., ()) is invalid because the second ) has no matching ().

Visual Description: Imagine the algorithm as traversing a binary tree. The root represents an empty string.

At Node A (string (), we have two choices: go left to add ( or right to add ).
If we have used n open brackets, the "left" branch is pruned (does not exist).
If the number of closed brackets equals the number of open brackets, the "right" branch is pruned.
The algorithm only visits nodes representing valid prefixes, significantly reducing the search space compared to the full binary tree of the brute force approach.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 22: Generate Parentheses Solution & Explanation

Problem Overview

TL;DR: We use backtracking to build strings character by character, maintaining a count of open and closed parentheses to ensure every generated string is valid by construction.

Brute Force Approach for Generate Parentheses

The naive approach attempts to generate every possible string of length 2n consisting of ( and ) characters, and then validates each string.

Naive Algorithm:

Generate all $2^{2n}$ sequences of length 2n.
Iterate through the list of sequences.
For each sequence, run a validation function (using a counter or stack) to check if it is well-formed.
If valid, add to the result list.

Pseudo-code:

text

function generate(current_string):
    if length of current_string == 2 * n:
        if isValid(current_string):
            add to results
        return

    generate(current_string + "(")
    generate(current_string + ")")

Algorithm Strategy: Backtracking Patterns

We define a recursive function backtrack that accepts the current string state and counters for the parentheses used.

State Variables:

current_string: The string built so far.
open_count: The number of ( used.
close_count: The number of ) used.
n: The total pairs required.

Logic:

Base Case: If the length of current_string is 2 * n, we have a complete, valid combination. Add it to the results and return.
Recursive Step (Open): If open_count < n, append ( and recurse with open_count + 1.
Recursive Step (Close): If close_count < open_count, append ) and recurse with close_count + 1.

By strictly following the condition close_count < open_count, we guarantee that at any point in the recursion, the prefix is valid, and we never generate a malformed string.

Execution Flow

Let's trace the execution for n = 2. Target length is 4.

Start: str="", open=0, close=0
Step 1: open < 2, add (.
- State: str="(", open=1, close=0
Step 2:
- Option A: open < 2, add (.
  - State: str="((", open=2, close=0
  - Next: open is not < 2. Only option is close.
  - Add ) -> str="(()", open=2, close=1
  - Add ) -> str="(())", open=2, close=2. Base Case Reached. Add to result.
- Option B: close < open (0 < 1), add ).
  - State: str="()", open=1, close=1
  - Next: close is not < open (1 is not < 1). Only option is open.
  - Add ( -> str="()(", open=2, close=1
  - Add ) -> str="()()", open=2, close=2. Base Case Reached. Add to result.

Final Result: ["(())", "()()"]

Proof of Correctness

The algorithm is correct because it exhaustively explores all valid decision paths while maintaining the property of well-formedness.

Validity: By ensuring close_count never exceeds open_count, we prevent prefixes like ()). By ensuring open_count never exceeds n, we ensure the correct count.
Completeness: The algorithm explores every possible valid addition at every step. Since we branch for both ( and ) whenever valid, no valid combination is omitted.

Pattern Reuse Notes

The logic used in LeetCode 22 applies to other problems requiring the generation of valid structural combinations:

LeetCode 301: Remove Invalid Parentheses: Uses similar logic to explore states, removing parentheses to reach a valid state.
Valid Parenthesis String (checking): The counter logic (open vs close) is the standard greedy approach for validating parenthesis strings.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 22

cpp

1class Solution {
2public:
3    vector<string> generateParenthesis(int n) {
4        vector<string> result;
5        string current;
6        backtrack(result, current, 0, 0, n);
7        return result;
8    }
9
10private:
11    void backtrack(vector<string>& result, string& current, int open, int close, int n) {
12        // Base case: if the string length is 2*n, we have a valid combination
13        if (current.length() == n * 2) {
14            result.push_back(current);
15            return;
16        }
17
18        // Decision 1: Add open parenthesis if we haven't used all of them
19        if (open < n) {
20            current.push_back('(');
21            backtrack(result, current, open + 1, close, n);
22            current.pop_back(); // Backtrack
23        }
24
25        // Decision 2: Add close parenthesis if valid (count < open count)
26        if (close < open) {
27            current.push_back(')');
28            backtrack(result, current, open, close + 1, n);
29            current.pop_back(); // Backtrack
30        }
31    }
32};

Java Solution for LeetCode 22

java

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    public List<String> generateParenthesis(int n) {
6        List<String> result = new ArrayList<>();
7        // Use StringBuilder for efficient mutation during backtracking
8        backtrack(result, new StringBuilder(), 0, 0, n);
9        return result;
10    }
11
12    private void backtrack(List<String> result, StringBuilder current, int open, int close, int n) {
13        // Base case: Valid string formed
14        if (current.length() == n * 2) {
15            result.add(current.toString());
16            return;
17        }
18
19        // Decision 1: Add open parenthesis
20        if (open < n) {
21            current.append('(');
22            backtrack(result, current, open + 1, close, n);
23            current.deleteCharAt(current.length() - 1); // Backtrack
24        }
25
26        // Decision 2: Add close parenthesis
27        if (close < open) {
28            current.append(')');
29            backtrack(result, current, open, close + 1, n);
30            current.deleteCharAt(current.length() - 1); // Backtrack
31        }
32    }
33}

Python Solution for LeetCode 22

python

1class Solution:
2    def generateParenthesis(self, n: int) -> List[str]:
3        result = []
4        
5        def backtrack(current_string, open_count, close_count):
6            # Base case: if string is complete
7            if len(current_string) == 2 * n:
8                result.append(current_string)
9                return
10
11            # Decision 1: Add open parenthesis
12            if open_count < n:
13                backtrack(current_string + "(", open_count + 1, close_count)
14
15            # Decision 2: Add close parenthesis
16            if close_count < open_count:
17                backtrack(current_string + ")", open_count, close_count + 1)
18        
19        # Start the recursion
20        backtrack("", 0, 0)
21        return result

Generate Parentheses

Core insight

Core Insight for Generate Parentheses

Full breakdown

LeetCode 22: Generate Parentheses Solution & Explanation

Problem Overview

Brute Force Approach for Generate Parentheses

Algorithm Strategy: Backtracking Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 22

Java Solution for LeetCode 22

Python Solution for LeetCode 22

Practise Generate Parentheses and the problems around it

Related problems

Generate Parentheses

Core insight

Core Insight for Generate Parentheses

Full breakdown

LeetCode 22: Generate Parentheses Solution & Explanation

Problem Overview

Brute Force Approach for Generate Parentheses

Algorithm Strategy: Backtracking Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 22

Java Solution for LeetCode 22

Python Solution for LeetCode 22

Practise Generate Parentheses and the problems around it

Related problems