Meta — Generate Parentheses (Backtracking All Combinations)

Problem Statement#

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

Constraints:

• 1 <= n <= 8
• Return all valid strings in any order

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

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

Why This Problem Matters#

Generate Parentheses (LeetCode 22) is one of Meta's most-asked medium problems, appearing in phone screens and onsite coding rounds consistently. Meta uses this to evaluate recursive thinking, constraint-based pruning, and the ability to enumerate valid states without brute-forcing invalid ones.

The problem is a gateway to understanding the Catalan number sequence — the number of valid parentheses strings with n pairs equals the nth Catalan number C(n). For n=8 that is 1430 strings, far fewer than the 2^(2n) = 65536 total binary strings. Pruning invalid branches early is what makes backtracking efficient here.

Amazon, Google, and Apple also ask this and its variants: generate all valid bracket combinations with multiple bracket types, or count valid parentheses strings given constraints. The core backtracking template is reusable across all of them.

The Core Insight#

At each position in the string being built, you have two choices: add an open parenthesis ( or add a close parenthesis ). Two constraints prune invalid branches:

1. You can only add ( if open < n — you have not used all n opens yet
2. You can only add ) if close < open — you cannot close more than you have opened

When open == n and close == n, the string is complete and valid — add it to results.

This guarantees every string generated is valid, and every valid string is generated exactly once.

Visual Dry Run#

n=2, backtracking tree (o=open count, c=close count):

Solution (Optimal)#

class Solution:
    def generateParenthesis(self, n: int) -> list:
        result = []
 
        def backtrack(current, open_count, close_count):
            if len(current) == 2 * n:
                result.append(current)
                return
            if open_count < n:
                backtrack(current + '(', open_count + 1, close_count)
            if close_count < open_count:
                backtrack(current + ')', open_count, close_count + 1)
 
        backtrack('', 0, 0)
        return result

var generateParenthesis = function(n) {
    const result = [];
 
    function backtrack(current, open, close) {
        if (current.length === 2 * n) {
            result.push(current);
            return;
        }
        if (open < n) backtrack(current + '(', open + 1, close);
        if (close < open) backtrack(current + ')', open, close + 1);
    }
 
    backtrack('', 0, 0);
    return result;
};

Time: O(4^n / sqrt(n)) — equals the nth Catalan number times O(n) per string construction Space: O(n) — recursion depth is at most 2n; result array holds Catalan(n) strings

Common Mistakes#

• Generating all 2^(2n) bit strings then filtering — exponentially worse than pruning during generation
• Using close > open instead of close < open as the pruning condition — inverted logic
• Using open > n instead of open < n as the expansion condition — off by one
• Mutating a shared array instead of concatenating strings — causes incorrect results due to shared state
• Not accounting for the base case: when string length hits 2*n, add to result and return

Interview Tips#

• Lead with the two constraints: "I can add ( if opens are left, and ) if closes are behind opens"
• Draw the decision tree for n=2 before coding — shows structured thinking
• Mention Catalan numbers if asked about time complexity — shows mathematical awareness
• For string building, concatenation is cleaner in Python; using a list and join is faster for large n
• Meta often asks "how many valid strings exist for n?" as a follow-up — answer is the nth Catalan number

Follow-up Questions#

• How many valid parentheses strings exist for n pairs? — nth Catalan number: C(n) = (2n)! / ((n+1)! * n!)
• How would you validate a parentheses string? — Stack or counter approach; increment on (, decrement on )
• How do you generate with multiple bracket types ({[]})? — Stack-based validity check in the pruning step
• What is the minimum cost to make a parentheses string valid? — Greedy scan or DP
• How would you find the longest valid parentheses substring? — Stack or DP on indices

Key Takeaways#

• The two pruning rules guarantee every generated string is valid and every valid string is generated once
• Rule 1: add ( only if open < n. Rule 2: add ) only if close < open
• Time complexity equals the Catalan number C(n) times O(n) per string — not O(4^n) after pruning
• This backtracking template is reusable: replace the constraint checks for any combinatorial generation problem
• Meta tests this to evaluate whether candidates understand constraint propagation in recursive search
• The number of valid strings grows as the nth Catalan number: 1, 2, 5, 14, 42, 132, 429, 1430 for n=1..8
• String concatenation in the recursive call avoids shared state bugs — use immutable string passing