Pattern Recognition Drill
Medium Backtracking
The Problem
Generate all combinations of n pairs of well-formed parentheses.
What approach would you use?
Think about it before scrolling down.
Track open and close counts. Add '(' if open < n. Add ')' if close < open. O(4^n / sqrt(n)).
Build from smaller n using dp[n] = '(' + dp[i] + ')' + dp[n-1-i]. Same complexity.
Common Trap
The constraint is close ≤ open ≤ n. Don't just generate all 2^(2n) strings and filter.