Generate Parentheses

Difficulty: Medium
Topics: String, Dynamic Programming, Backtracking
Link: https://leetcode.com/problems/generate-parentheses/

Problem Description

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

1 <= n <= 8

Solution

1. Problem Deconstruction (500+ words)

Technical Restatement
Given an integer ( n ), generate all binary strings of length ( 2n ) composed of exactly ( n ) opening parentheses ‘(’ and ( n ) closing parentheses ‘)’, such that the string is valid. A valid parentheses string is defined recursively:

The empty string is valid.
If ( A ) is valid, then the concatenation “(” + ( A ) + “)” is valid.
If ( A ) and ( B ) are valid, then the concatenation ( A + B ) is valid.

Algorithmically, validity is equivalent to the condition that for every prefix of the string, the number of ‘(’ is greater than or equal to the number of ‘)’, and the total counts are equal. This is a classic enumeration problem yielding the Catalan number ( C_n = \frac{1}{n+1} \binom{2n}{n} ) possible strings.

Beginner Restatement
You have ( n ) pairs of parentheses. Your task is to list every possible arrangement that “makes sense” grammatically: every opening parenthesis must eventually be closed, and you cannot close a parenthesis before opening it. For example, when ( n = 2 ), the valid arrangements are “(())” and “()()”. Invalid arrangements like “)(” or “())(” are not allowed. Think of it as writing all possible correctly nested structures using ( n ) pairs.

Mathematical Restatement
Let ( \Sigma = { (, ) } ) and ( S \subset \Sigma^{2n} ) be the set of all strings ( s ) with ( |s|( = n ) and ( |s|) = n ). Define the balance of a prefix ( s[1…i] ) as ( \text{bal}(i) = #{(} - #{)} ). Then the set of valid strings is:
[ V_n = \left{ s \in S : \forall i \in [1,2n], \text{bal}(i) \geq 0 \right} ] The cardinality ( |V_n| = C_n ), the ( n )-th Catalan number. The problem requires generating ( V_n ) explicitly.

Constraint Analysis

( 1 \leq n \leq 8 ).
- Impact on Solutions: The output size grows as ( C_n ), which for ( n=8 ) is 1430 strings of length 16. This is modest, allowing exponential-time algorithms (e.g., brute force ( 2^{16} = 65536 ) candidates) to run within limits. Backtracking with pruning is efficient.
- Hidden Edge Cases:
  1. ( n=1 ) is the minimal non-empty case, yielding exactly one string “()”.
  2. The empty string (for ( n=0 )) is not required by constraints but often appears in recursive formulations.
  3. Duplicate generation is impossible if the algorithm follows a disciplined construction (e.g., maintaining counts).
  4. Memory for storing all strings is negligible (~22 KB for ( n=8 )).
  5. The upper bound ( n=8 ) ensures that even naive recursion without memoization will not cause stack overflow (depth ≤ 16).

2. Intuition Scaffolding

Analogies

Real-World Metaphor (Construction Crane): Imagine you have ( n ) construction tasks, each requiring a “start” signal ‘(’ and a “stop” signal ‘)’. You must start a task before stopping it, and you can have multiple tasks running concurrently. The sequence of start/stop signals must never stop a task that hasn’t started, and by the end all tasks must be stopped. The valid sequences correspond to all possible schedules.
Gaming Analogy (Magic Spell Casting): You have ( n ) spells, each requiring a “charge” (‘(’) and a “cast” (‘)’). You can charge multiple spells sequentially, but casting must happen in reverse order (last charged, first cast). The sequence of charges and casts must never cast more spells than are currently charged. Valid sequences are all possible casting orders that respect this stack discipline.
Math Analogy (Lattice Paths): Consider a grid from (0,0) to (n,n). Moving right represents ‘(’, moving up represents ‘)’. A valid parentheses string corresponds to a path that never crosses above the diagonal (i.e., stays in the region ( y \leq x )). The number of such paths is the Catalan number. Generating all valid strings is equivalent to generating all such monotonic lattice paths.

Common Pitfalls

Permuting All Parentheses: Generating all ( \binom{2n}{n} ) sequences of ‘(’ and ‘)’ and filtering for validity yields duplicates and wastes time on invalid prefixes.
Greedy Nesting: Always nesting parentheses (e.g., “(((…)))”) misses non-nested forms like “()()()…”.
Ignoring Balance Midway: Adding ‘)’ unconditionally when counts are equal can lead to invalid strings like “())(”.
Incorrect Dynamic Programming Combining: Trying to generate new strings by simply wrapping previous strings with “(” and “)” may miss strings like “(())(())” for ( n=4 ).
Overcounting via Recursive Insertion: Inserting “()” into every position of every smaller valid string can produce duplicates (e.g., “()()” from inserting into “()” at position 0 or 2).
Assuming 2^n Possibilities: The number of valid strings is far less than ( 2^{2n} ) due to the balance constraint.

3. Approach Encyclopedia

1. Brute Force Generation & Validation

Concept: Enumerate all ( 2^{2n} ) binary strings of ‘(’ and ‘)’, then validate each using a stack or balance counter.

Pseudocode:

def brute_force(n):
    results = []
    def generate_all(current):
        if len(current) == 2*n:
            if valid(current):
                results.append(current)
        else:
            generate_all(current + '(')
            generate_all(current + ')')
    def valid(s):
        balance = 0
        for ch in s:
            balance += 1 if ch == '(' else -1
            if balance < 0:
                return False
        return balance == 0
    generate_all('')
    return results

Complexity Proof:
Time: ( O(2^{2n} \cdot 2n) = O(n \cdot 4^n) ). There are ( 2^{2n} ) leaves, each string built in ( O(2n) ) time, and validation is ( O(2n) ).
Space: ( O(n) ) recursion depth, plus ( O(C_n \cdot 2n) ) for output.

Visualization (n=2):

Tree leaves (length 4):
((((, (((), (()(, (()), ()((, ()(), ())(, ())), )(((, )((), )()(, )()), ))((, ))(), )))(, ))))
Valid: (()) and ()() only.

2. Backtracking with Pruning (DFS)

Concept: Build strings incrementally, only adding ‘)’ if it would not violate the balance condition.

Pseudocode:

def backtracking(n):
    res = []
    def dfs(s, open_cnt, close_cnt):
        if len(s) == 2*n:
            res.append(s)
            return
        if open_cnt < n:
            dfs(s + '(', open_cnt + 1, close_cnt)
        if close_cnt < open_cnt:
            dfs(s + ')', open_cnt, close_cnt + 1)
    dfs('', 0, 0)
    return res

Complexity Proof:
Time: ( O\left(\frac{4^n}{\sqrt{n}} \cdot n\right) ) — each of the ( C_n ) strings is built in ( O(n) ) time.
Space: ( O(n) ) recursion stack, output excluded.

Visualization (n=2):

dfs('',0,0)
  → dfs('(',1,0)
      → dfs('((',2,0)
          → dfs('(()',2,1)
              → dfs('(())',2,2) ✓
      → dfs('()',1,1)
          → dfs('()(',2,1)
              → dfs('()()',2,2) ✓

3. Dynamic Programming (Closure Number)

Concept: Every valid string can be uniquely written as “(” + ( A ) + “)” + ( B ), where ( A ) and ( B ) are valid strings with ( |A| + |B| = n-1 ) pairs. Use DP to store solutions for smaller ( n ).

Pseudocode:

def dp(n):
    dp = [[] for _ in range(n + 1)]
    dp[0] = ['']
    for i in range(1, n + 1):
        for j in range(i):
            for left in dp[j]:
                for right in dp[i - 1 - j]:
                    dp[i].append('(' + left + ')' + right)
    return dp[n]

Complexity Proof:
Time: ( O(n \cdot C_n) ) — each of the ( C_n ) strings is constructed by concatenating two smaller strings, total operations proportional to sum of Catalan numbers.
Space: ( O(C_n \cdot 2n) ) to store all strings across all dp states.

Visualization (n=3):

dp[0]: ['']
dp[1]: [()]  
dp[2]: [()(), (())]  
dp[3]: combinations:
  j=0: '(' + '' + ')' + dp[2] → ()()(), ()(())
  j=1: '(' + dp[1] + ')' + dp[1] → (())()
  j=2: '(' + dp[2] + ')' + '' → ((())), (()())
Result: ["((()))","(()())","(())()","()(())","()()()"]

4. Iterative via Stack Simulation

Concept: Use an explicit stack to simulate the DFS, avoiding recursion.

Pseudocode:

def iterative(n):
    stack = [('', 0, 0)]
    res = []
    while stack:
        s, open_cnt, close_cnt = stack.pop()
        if len(s) == 2*n:
            res.append(s)
        else:
            if open_cnt < n:
                stack.append((s + '(', open_cnt + 1, close_cnt))
            if close_cnt < open_cnt:
                stack.append((s + ')', open_cnt, close_cnt + 1))
    return res

Complexity: Same as backtracking, but with explicit stack.

4. Code Deep Dive

Optimal Solution (Backtracking) with Annotations

def generateParenthesis(n: int):
    """
    Generates all combinations of well-formed parentheses for n pairs.
    
    Args:
        n: integer number of parenthesis pairs (1 ≤ n ≤ 8)
    
    Returns:
        List of strings, each of length 2n, representing valid combinations.
    """
    result = []  # stores the final valid strings
    
    def backtrack(current: str, open_used: int, close_used: int):
        """
        Recursively builds valid strings.
        
        Args:
            current: the string built so far
            open_used: number of '(' used
            close_used: number of ')' used
        """
        # Base case: if the string length equals 2n, it is complete and valid.
        if len(current) == 2 * n:
            result.append(current)
            return
        
        # Decision 1: Add '(' if we haven't used all n opening parentheses.
        # This ensures we never exceed n opening parentheses.
        if open_used < n:
            # Explore the branch with an added '('
            backtrack(current + "(", open_used + 1, close_used)
        
        # Decision 2: Add ')' only if the number of ')' used is less than '(' used.
        # This guarantees that every closing parenthesis matches a previous opening one,
        # maintaining prefix validity.
        if close_used < open_used:
            backtrack(current + ")", open_used, close_used + 1)
    
    # Start the recursion with an empty string and zero counts.
    backtrack("", 0, 0)
    return result

Edge Case Handling

n = 1: The recursion tree:
- Start: ("",0,0) → add ‘(’ → ("(",1,0) → can only add ‘)’ (since close_used=0 < open_used=1) → ("()",1,1) → length=2 → add to result. Output: ["()"].
n = 0 (not required): Would immediately hit base case and return [""].
Max n = 8: The recursion depth is at most 16, safe for Python recursion limit (default 1000).
String Building: Each recursive call creates a new string (immutable in Python). This is acceptable for n ≤ 8 but could be optimized with a mutable list and ''.join() for larger n.

5. Complexity War Room

Hardware-Aware Analysis

For ( n=8 ):
- Number of strings: ( C_8 = 1430 ).
- Each string length: 16 characters.
- Total output size: ( 1430 \times 16 = 22,880 ) bytes ≈ 22.9 KB.
- Fits comfortably in L1 cache (typically 32–64 KB).
- Recursion depth 16 → stack frame size ~ O(1) per frame → negligible memory.
- Python string creation overhead is acceptable given the small scale.

Industry Comparison Table

Approach	Time Complexity	Space Complexity (excl. output)	Readability	Interview Viability
Brute Force	( O(n \cdot 4^n) )	( O(n) )	9/10 (simple)	❌ (fine for small n, but not optimal)
Backtracking (DFS)	( O\left(\dfrac{4^n}{\sqrt{n}}\right) )	( O(n) )	10/10 (elegant)	✅ (gold standard)
Dynamic Programming	( O(n \cdot C_n) )	( O(C_n \cdot n) ) (for DP table)	7/10 (requires insight)	✅ (demonstrates DP skill)
Iterative Stack	same as backtracking	( O(n \cdot C_n) ) (stack size)	8/10 (explicit control)	✅ (if recursion is discouraged)

Note: ( C_n \approx \dfrac{4^n}{n^{3/2} \sqrt{\pi}} )

6. Pro Mode Extras

Variants

Count Valid Strings (No Generation): Use Catalan formula ( C_n = \frac{1}{n+1}\binom{2n}{n} ) or DP with integer counts.
Generate in Lexicographic Order: Backtracking already does this because ‘(’ < ‘)’ and we try ‘(’ first.
Valid Parentheses with Multiple Types (e.g., ()[]{}): Extend backtracking to track separate counts and a stack of open types.
Generate All Valid Strings of Length 2n with k Mismatches: Allow up to k positions where the prefix condition is violated? This becomes a constrained enumeration problem.
Minimum Insertions to Make Valid: Given a string, find the minimum insertions of ‘(’ or ‘)’ to make it valid (LeetCode 921).
Longest Valid Substring: Find the length of the longest valid parentheses substring in a given string (LeetCode 32).

Interview Cheat Sheet

Immediate Steps:
1. Confirm understanding: “We need all strings of n ‘(’ and n ‘)’ that are valid.”
2. Mention Catalan number to show combinatorial awareness.
3. Start with brute force idea, then optimize via backtracking.
4. Draw recursion tree for n=2 to illustrate pruning.
Key Points to Articulate:
- “We can only add ‘)’ if there are more ‘(’ used than ‘)’.”
- “The number of valid strings is the Catalan number, which grows exponentially but manageably for n≤8.”
- “Backtracking ensures we only explore valid prefixes, drastically pruning the search.”
Code Tips:
- Use if close < open: not if close < n: for the closing condition.
- Consider using a list to build the string and ''.join() for efficiency in larger n.
If Stuck:
- Think of the problem as generating all paths in a binary tree of depth 2n with constraints.
- Relate to stack operations: each ‘(’ pushes, each ‘)’ pops, and the stack must never underflow.

This structured approach ensures a comprehensive understanding from brute force to optimal solution, with practical insights for interviews and real-world implementation.

#22 - Generate Parentheses

Generate Parentheses

Problem Description

Solution

1. Problem Deconstruction (500+ words)

2. Intuition Scaffolding

3. Approach Encyclopedia

4. Code Deep Dive

5. Complexity War Room

6. Pro Mode Extras