Generate Parentheses
Signals to notice
Brute force first
Generate all 2^(2n) strings of '(' and ')' and filter valid ones — exponential waste. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
Backtracking: track open and close counts. Add '(' if open < n, add ')' if close < open. When length = 2n, record the combination. — the Catalan number. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.
What must stay true
At any point, close count ≤ open count ≤ n. This constraint ensures every generated string is valid — you never close a bracket that wasn't opened. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.
Easy way to go wrong
Adding ')' when close ≥ open — that creates an invalid string. The constraint close < open before adding ')' guarantees validity. The fix is usually to return to the meaning of each move, not just the steps themselves.