Generate Parentheses LeetCode #22: Backtracking Walkthrough

Generate parentheses leetcode problem #22 is one of the most elegant backtracking problems you will encounter. Unlike problems that generate all possibilities and then filter out invalid ones, this problem uses two simple constraints to produce ONLY valid combinations from the start.

The beauty of Generate Parentheses is that it distills backtracking to its purest form: at each step, you have at most two choices — add an open parenthesis or add a close parenthesis — and the constraints tell you exactly when each choice is legal. No visited set, no duplicate handling, no sorting needed.

By the end of this walkthrough, you will understand how constraint-based generation works and why it is far more efficient than brute-force filtering. YeetCode flashcards can help you internalize these two rules until they become second nature.

Given n pairs of parentheses, generate all combinations of well-formed parentheses. For n=3, the answer is ["((()))","(()())","(())()","()(())","()()()"]. Each combination has exactly n open parentheses and n close parentheses, and at every prefix the number of open parentheses is greater than or equal to the number of close parentheses.

This is fundamentally a counting problem tied to the Catalan numbers. The number of valid combinations for n pairs is C(n) = (2n)! / ((n+1)! * n!). For n=3 that is 5, for n=4 it is 14, and the count grows rapidly.

The naive approach would generate all 2^(2n) binary strings of length 2n (choosing open or close at each position), then filter to keep only valid ones. For n=10, that means checking over one million strings to keep just 16,796 valid ones. Constraint-based backtracking avoids this waste entirely.

The entire algorithm rests on two rules applied at each step of the recursion. Rule 1: you can add an open parenthesis "(" if the count of open parentheses used so far is less than n. Rule 2: you can add a close parenthesis ")" if the count of close parentheses used so far is less than the count of open parentheses.

The base case is equally simple: when the current string has length 2n, you have placed all n open and n close parentheses, and the constraints guarantee the result is valid. Add it to the output and return.

Why do these two rules guarantee well-formedness? Rule 1 prevents using more than n open parens. Rule 2 ensures you never close a parenthesis that was not opened — because close can only increment when it trails behind open. Together they make it impossible to produce an invalid combination.

The implementation uses a recursive backtrack function that takes three parameters: the current string being built, the count of open parentheses placed, and the count of close parentheses placed. At each call, you check the two rules and recurse accordingly.

When open < n, you recurse with the current string plus "(" and open + 1. When close < open, you recurse with the current string plus ")" and close + 1. These are not mutually exclusive — both branches can fire at the same step, creating the decision tree.

The time complexity is O(4^n / sqrt(n)), which is the nth Catalan number — this represents the exact number of valid combinations. Space complexity is O(n) for the recursion stack depth, since each combination has length 2n and the tree depth is 2n.

Walking through n=3 reveals the decision tree in action. The root starts with an empty string, open=0, close=0. Only Rule 1 applies (open < 3), so you add "(". Now current="(", open=1, close=0.

From "(", both rules apply: open < 3 allows "((" and close < open allows "()". This is the first real branch. Following the left path to "((" then "(((" — at this point open=3 so only Rule 2 applies. You keep adding close parens: "((()))" is the first complete combination.

Backtracking from "(((" to "((" where close=0, you can add ")": "(()". From "(()": open < 3 allows "(()(", and close < open allows "(())". The "()()" branch follows. Eventually all five combinations emerge: ((())), (()()), (())(), ()(()), ()()().

Notice that the tree never generates invalid strings like ")(", "))(", or "())(" — the constraints prune those branches before they even start. This is the power of constraint-based backtracking versus generate-and-filter.

For n=1, there is exactly one valid combination: "()". Your backtracking should produce this single-element array. For n=0, the answer is [""] — one combination of zero pairs, which is the empty string. Some implementations return an empty array for n=0, but the Catalan number C(0) = 1, meaning one valid combination exists.

For n=2, the two valid combinations are "(())" and "()()". This is a useful sanity check because it is small enough to trace by hand. Verify that your solution produces exactly these two and no duplicates.

The constraint n <= 8 in the LeetCode problem means the maximum output size is C(8) = 1430 combinations. Performance is rarely an issue, but the Catalan growth means n=15 would produce over 9 million combinations — understanding the complexity helps explain why the problem caps n at 8.

Generate Parentheses teaches constraint-based backtracking — the most elegant variant of the backtracking pattern. Instead of generating candidates and filtering, you embed the validity rules directly into the recursion. The constraints themselves prevent invalid states from ever being explored.

This is different from problems like Subsets (#78) or Permutations (#46) where you need visited sets or index tracking. In Generate Parentheses, the open and close counts ARE the state, and the two inequality checks ARE the pruning. No additional data structures needed.

Once you internalize this pattern, look for it in other problems: generating valid IP addresses, balanced binary trees, and any problem where simple rules constrain which choices are valid at each step. Review Generate Parentheses with YeetCode flashcards until the two rules are automatic — they form the foundation for all constraint-based generation problems.