LeetCode Generate Parentheses: Counting Backtrack

Generate Parentheses (LeetCode 22, Medium) is the cleanest counting-backtrack problem in the catalog. The whole solution rides on two inequalities. Once you see them, the code writes itself.

The Problem

Given n pairs of parentheses, generate all combinations of well-formed parentheses.

Example:

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

Brute Force

Generate all 2^(2n) binary strings of length 2n, then filter those that are balanced.

def generate_brute(n):
    result = []
    def gen(s):
        if len(s) == 2 * n:
            if valid(s):
                result.append(s)
            return
        gen(s + '(')
        gen(s + ')')
    def valid(s):
        bal = 0
        for ch in s:
            bal += 1 if ch == '(' else -1
            if bal < 0:
                return False
        return bal == 0
    gen('')
    return result

Correct but explores invalid prefixes for no reason.

Optimal Solution

Track the number of opens and closes used so far. Two simple rules:

1. Add ( while open < n.
2. Add ) while close < open.

def generate_parenthesis(n):
    result = []
    def backtrack(s, opens, closes):
        if len(s) == 2 * n:
            result.append(s)
            return
        if opens < n:
            backtrack(s + '(', opens + 1, closes)
        if closes < opens:
            backtrack(s + ')', opens, closes + 1)
    backtrack('', 0, 0)
    return result

No invalid partials, no post-filter.

Walk Through an Example

n = 2. Start s='', opens=0, closes=0.

• Add (: s='(', opens=1, closes=0.
  • Add (: s='((', opens=2.
    • Cannot add (, opens==n. Add ): s='(()', closes=1.
      • Add ): s='(())'. Record.
  • Add ): s='()', closes=1.
    • Add (: s='()(', opens=2. Add ): s='()()'. Record.

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

Edge Cases

• n = 0: return [""], one empty string. Some implementations return an empty list; check the problem statement.
• n = 1: returns ["()"].
• Very large n: the answer count is the n-th Catalan number, which grows roughly as 4^n / n^(3/2). Memory becomes the bottleneck.

Complexity Analysis

• Time: O(4^n / sqrt(n)). The output size equals the n-th Catalan number, and each string is length 2n.
• Space: O(n) recursion depth, plus output size.

The brute force is O(2^(2n) * n) because of the filter step.

How to Explain It in an Interview

State the invariants first: “A prefix is extensible to a valid string if and only if opens <= n and closes <= opens.” From those two inequalities, the two recursive branches drop out. Mention that you’re avoiding the brute filter by encoding validity into the recursion itself. Note the Catalan complexity briefly to show you know it’s an optimal enumeration bound.

Related Problems

• LeetCode 20 Valid Parentheses (stack)
• LeetCode 32 Longest Valid Parentheses (DP)
• LeetCode 301 Remove Invalid Parentheses
• LeetCode 678 Valid Parenthesis String

Wrap up

Generate Parentheses is the canonical “constraint-driven backtracking” problem. The two-count invariant pattern reappears all over combinatorial search. Once you write it from scratch in two minutes, you’ve internalized a pattern that pays off in dozens of related problems.