Generate Parentheses LeetCode 22 Deep Dive

LeetCode 22 — Generate Parentheses — gives you an integer n and asks you to generate all combinations of well-formed (valid) parentheses using exactly n pairs. A string of parentheses is well-formed if every open parenthesis has a matching close parenthesis and the brackets are properly nested. For n=1 there is one result: "()", for n=2 there are two: "(())" and "()()", and for n=3 there are five.

The problem is rated Medium on LeetCode and appears in the NeetCode 150 stack and backtracking sections. The naive approach of generating all 2^(2n) binary strings and filtering for validity is too slow. The key insight is to build valid strings character by character during backtracking — only extend when the extension keeps the string valid. This prunes the search space dramatically.

Understanding this problem gives you the backtracking template for constraint-guided generation. The same open/close counting pattern reappears in Valid Parentheses, Remove Invalid Parentheses, and Score of Parentheses. The result count — the nth Catalan number — connects this problem to a surprising family of combinatorial structures.

The backtracking approach builds the result string one character at a time. It tracks two counters: open (how many "(" have been added so far) and close (how many ")" have been added so far). At each recursive call, you choose to add either "(" or ")" based on two simple rules: add "(" if open < n, add ")" if close < open. When the string reaches length 2n, it is a complete valid combination and is added to the results.

The base case is len(current) == 2*n, at which point the current string is guaranteed to be valid — the two constraints ensure no invalid string can ever be completed. The recursion tree has at most 2^(2n) leaves before pruning, but the constraints cut it down to only the Catalan number of valid leaves. Each valid leaf is reached exactly once, and the path to it is the unique valid string.

This is fundamentally different from a "generate then filter" approach. You never build an invalid string — the constraints prevent it at every step. Every leaf in the pruned recursion tree is a valid answer, and every valid answer corresponds to exactly one leaf. The time complexity is O(4^n / sqrt(n)) — the sum of lengths of all results, which matches the nth Catalan number times 2n.

Visualize the backtracking as a binary decision tree. Each node holds the current string and the (open, close) counts. From any node, you branch left by adding "(" (if open < n) and branch right by adding ")" (if close < open). Nodes where neither branch is available and the string is incomplete are dead ends — they are pruned and never reached under the constraint rules.

For n=2, the tree starts at ("", 0, 0). From there: add "(" → ("(", 1, 0). From that: add "(" → ("((", 2, 0), or add ")" → ("()", 1, 1). From ("((", 2, 0): can only add ")" → ("(()", 2, 1) → "(())" (complete). From ("()", 1, 1): add "(" → ("()(", 2, 1) → "()()" (complete). The tree naturally produces exactly 2 leaves for n=2, both valid.

Each leaf in the tree sits at depth 2n and represents one valid combination. Internal nodes at depth less than 2n always have at least one valid child — the constraints guarantee the tree never gets stuck at a non-leaf before reaching depth 2n. The number of leaves equals the nth Catalan number: 1, 2, 5, 14, 42 for n = 1, 2, 3, 4, 5.

The number of valid combinations of n pairs of parentheses is the nth Catalan number: C(n) = (2n)! / ((n+1)! * n!). For small values: C(1) = 1, C(2) = 2, C(3) = 5, C(4) = 14, C(5) = 42, C(6) = 132. These are the exact counts you see when you run Generate Parentheses for each n. The growth rate is approximately 4^n / (n^1.5 * sqrt(pi)), meaning the output size grows exponentially — you cannot do better than O(Catalan(n)) time since you must output every result.

The Catalan numbers arise whenever you count the number of ways to correctly match n pairs of something. For parentheses, each valid string corresponds to a unique "ballot sequence" — a sequence where at every prefix, the number of "(" is >= the number of ")". This is the same as counting paths from (0,0) to (n,n) on a grid that never cross the diagonal, which equals C(n).

The closed-form formula C(n) = (2n)! / ((n+1)! * n!) can also be written as C(n) = (1/(n+1)) * binomial(2n, n). For n=3: (1/4) * (6! / (3! * 3!)) = (1/4) * 20 = 5. For n=4: (1/5) * (8! / (4! * 4!)) = (1/5) * 70 = 14. These numbers grow roughly as 4^n / n^1.5, so for n=8 (the LeetCode constraint maximum) there are C(8) = 1430 valid combinations.

An iterative dynamic programming approach builds valid strings of length 2n bottom-up from valid strings of smaller sizes. Define dp[k] as the list of all valid parenthesizations for k pairs. The base case is dp[0] = [""]. For each k from 1 to n, dp[k] is constructed by iterating over all splits i from 0 to k-1: for each i, every string in dp[i] can be wrapped inside outer parens and concatenated with every string in dp[k-1-i]. The formula is dp[k] += "(" + p + ")" + q for all p in dp[i] and q in dp[k-1-i].

This recurrence reflects the Catalan structure: every valid string of n pairs begins with "(" and the matching ")" appears somewhere in the middle, splitting the string into an "inner" part (i pairs) and a "tail" part (n-1-i pairs). By iterating over all possible positions of the first matching close paren, you generate every valid string exactly once.

The DP approach produces the same result as backtracking — the same Catalan number of strings — but avoids recursion entirely. It is less intuitive for most interview settings because the recurrence requires understanding the Catalan decomposition, but it can be useful when the call stack depth is a concern or when building on previous results is advantageous. Both approaches have the same asymptotic time complexity of O(4^n / sqrt(n)).

Python solution using backtracking: def generateParenthesis(n): res = []; def bt(s, open, close): if len(s) == 2*n: res.append(s); return; if open < n: bt(s+"(", open+1, close); if close < open: bt(s+")", open, close+1); bt("", 0, 0); return res. The function builds the string with concatenation s+"(" and s+")" rather than a mutable list with append/pop — this is cleaner because strings are immutable and each recursive call receives its own copy of s without needing explicit backtracking (no pop needed). Time O(4^n / sqrt(n)), space O(n) for the recursion stack depth (the deepest path is 2n frames).

Java solution: public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); bt(res, "", 0, 0, n); return res; } private void bt(List<String> res, String s, int open, int close, int n) { if (s.length() == 2*n) { res.add(s); return; } if (open < n) bt(res, s+"(", open+1, close, n); if (close < open) bt(res, s+")", open, close+1, n); }. Java String concatenation creates a new String object at each call, which is acceptable here since strings are short (length at most 2*8 = 16 for n <= 8) and the total work is bounded by the Catalan number.

Both solutions have identical logic: the two if-guards replace explicit validity checking, string concatenation replaces StringBuilder with explicit undo, and the base case appends the completed string. The Python solution is about 8 lines, the Java solution about 10. Both pass all LeetCode 22 test cases with excellent performance — the pruned backtracking tree is much smaller than the full 2^(2n) binary tree. For n=8, only 1430 strings are generated out of 2^16 = 65,536 possible binary strings of length 16.

N-Queens (LeetCode 51) is the classic backtracking problem: place n queens on an n×n board with no two queens attacking each other. Like Generate Parentheses, it builds a solution incrementally (one queen per row) with constraint checks at each step (no column or diagonal conflict). The backtracking template — choose, constrain, recurse, unchoose — is identical. Both problems have exponentially many possibilities before pruning but polynomial-sized solution spaces relative to n.

Combination Sum (LeetCode 39) generates all combinations of candidate numbers that sum to a target, allowing reuse of elements. Letter Combinations of a Phone Number (LeetCode 17) generates all strings that a digit sequence could represent. Both share the backtracking structure: iterate over choices, recurse with a modified state, then undo the choice. Generate Parentheses is unusual in that the undo step is implicit — string immutability handles it automatically.

The backtracking family on LeetCode includes subsets, permutations, combinations, word search, and Sudoku solver. Generate Parentheses sits at the easy end of this family due to its simple two-rule constraint. Mastering the open/close counter pattern and recognizing the Catalan number in the result count prepares you for the harder backtracking problems where multiple constraint types interact. The key skill is identifying what state to track and what constraints to enforce at each recursive step.