Missing undo step on backtrack
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.
A complete visual walkthrough of backtracking with constraints — from brute force to elegant recursion.
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 <= 8The naive approach generates all 22n strings of ( and ), then filters for valid ones. For n = 2, that means 24 = 16 strings, but only 2 are valid:
... and 10 more invalid combinations. Only 2 out of 16 pass validation. For n = 3, it is 5 out of 64. For n = 10, only 16,796 out of 1,048,576. The vast majority are wasted work.
Validation requires checking that at every prefix, the count of ) never exceeds the count of (, and the total counts are equal. This brute force runs in O(22n * n) time — far too slow.
The problem: we generate strings we know are invalid. What if we could avoid generating them altogether? Instead of "generate then validate," we can "validate as we build."
Instead of generating all combinations and filtering, we build the string one character at a time, applying two simple rules at each position:
These two rules guarantee that every string we generate is valid. We never explore a dead-end path. This is backtracking — we try a choice, recurse, then undo the choice and try the alternative.
At each step, we branch into at most two choices. Branches that violate the rules are pruned — never explored.
Backtracking = DFS with pruning. We explore the decision tree depth-first, but the constraints prune invalid subtrees before we ever visit them. The result: we only generate the exact set of valid parenthesizations — nothing more.
Let's trace the full decision tree for n = 2. Each node shows the current string, with the counts (open, close). Green leaves are valid results. Red dashed branches are pruned.
The tree starts at "". At each node we try adding ( and ) where the rules allow. Red dashed branches are pruned — never explored. Green leaves are valid results collected.
For n = 2, the tree produces exactly 2 valid strings: (()) and ()(). Notice how the first character is always ( — you can never start with ) because close (0) is not less than open (0).
The number of valid combinations is the n-th Catalan number: C(n) = (2n)! / ((n+1)! * n!). For n=3 that is 5, for n=4 it is 14. The Catalan numbers grow much slower than 22n, confirming that backtracking avoids enormous waste.
"" to results. Output: [""]"" → ( → ().No special-case code needed. The constraints open < n and close < open naturally handle all edge cases. When n = 0, neither condition is true at the start, so we immediately hit the base case.
class Solution { public List<String> generateParenthesis(int n) { List<String> result = new ArrayList<>(); backtrack(result, new StringBuilder(), 0, 0, n); return result; } private void backtrack( List<String> result, StringBuilder sb, int open, // count of '(' placed so far int close, // count of ')' placed so far int n // target pairs ) { // Base case: string is complete if (sb.length() == 2 * n) { result.add(sb.toString()); return; } // Choice 1: add '(' if we haven't used all n if (open < n) { sb.append('('); backtrack(result, sb, open + 1, close, n); sb.deleteCharAt(sb.length() - 1); // undo choice } // Choice 2: add ')' if it won't create imbalance if (close < open) { sb.append(')'); backtrack(result, sb, open, close + 1, n); sb.deleteCharAt(sb.length() - 1); // undo choice } } }
func generateParenthesis(n int) []string { result := []string{} var backtrack func(sb []byte, open, close int) backtrack = func(sb []byte, open, close int) { // Base case: string is complete if len(sb) == 2*n { result = append(result, string(sb)) return } // Choice 1: add '(' if we haven't used all n if open < n { backtrack(append(sb, '('), open+1, close) } // Choice 2: add ')' if it won't create imbalance if close < open { backtrack(append(sb, ')'), open, close+1) } } backtrack([]byte{}, 0, 0) return result }
class Solution: def generate_parenthesis(self, n: int) -> list[str]: result: list[str] = [] def backtrack( sb: str, open_count: int, # count of '(' placed so far close_count: int # count of ')' placed so far ) -> None: # Base case: string is complete if len(sb) == 2 * n: result.append(sb) return # Choice 1: add '(' if we haven't used all n if open_count < n: backtrack(sb + '(', open_count + 1, close_count) # Choice 2: add ')' if it won't create imbalance if close_count < open_count: backtrack(sb + ')', open_count, close_count + 1) backtrack('', 0, 0) return result
impl Solution { pub fn generate_parenthesis(n: i32) -> Vec<String> { let mut result = Vec::new(); Self::backtrack(&mut result, String::new(), 0, 0, n); result } fn backtrack( result: &mut Vec<String>, sb: String, open: i32, // count of '(' placed so far close: i32, // count of ')' placed so far n: i32, // target pairs ) { // Base case: string is complete if sb.len() == (2 * n) as usize { result.push(sb); return; } // Choice 1: add '(' if we haven't used all n if open < n { let mut s = sb.clone(); s.push('('); Self::backtrack(result, s, open + 1, close, n); } // Choice 2: add ')' if it won't create imbalance if close < open { let mut s = sb.clone(); s.push(')'); Self::backtrack(result, s, open, close + 1, n); } } }
function generateParenthesis(n: number): string[] { const result: string[] = []; function backtrack( sb: string, open: number, // count of '(' placed so far close: number // count of ')' placed so far ): void { // Base case: string is complete if (sb.length === 2 * n) { result.push(sb); return; } // Choice 1: add '(' if we haven't used all n if (open < n) { backtrack(sb + '(', open + 1, close); } // Choice 2: add ')' if it won't create imbalance if (close < open) { backtrack(sb + ')', open, close + 1); } } backtrack('', 0, 0); return result; }
Why StringBuilder? Using a mutable StringBuilder with append/delete is more efficient than string concatenation. Each recursive call modifies and then restores the builder — the classic backtracking pattern of "choose, explore, un-choose."
Enter a value for n and watch the backtracking algorithm explore the decision tree step by step.
The number of valid parenthesizations of n pairs is the n-th Catalan number, C(n) = (2n)! / ((n+1)! · n!). By Stirling's approximation, C(n) ≈ 4n / (n√n). Each valid string has length 2n, so generating all of them costs O(4n / √n). The recursion depth is at most 2n and the StringBuilder holds at most 2n characters, giving O(n) auxiliary space (excluding the output list itself).
Generates all 22n binary strings of parentheses, then validates each one in O(n) by scanning for balanced prefixes. The recursion depth is 2n, using O(n) stack space, but the vast majority of generated strings are invalid.
Only the n-th Catalan number C(n) of valid strings are generated, each of length 2n. By Stirling's approximation C(n) grows as 4n/(n√n). The recursion tree is pruned by the two constraints, and the StringBuilder uses at most 2n characters, giving O(n) auxiliary space.
The Catalan number C(n) = 4n / (n√n) counts exactly the valid parenthesizations. Brute force generates all 22n binary strings and filters, wasting exponentially more work. Backtracking generates only the C(n) valid strings -- no invalid path is ever explored -- making it an exponential improvement despite the output still being exponential.
Review these before coding to avoid predictable interview regressions.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.