The problem sounds trivial until you try to code it under pressure. Given n pairs of parentheses, return every well-formed string you can build with them. For n = 3 that’s ((())), (()()), (())(), ()(()), and ()()(). Five strings. The count climbs fast, and the way most people first reach for it is the way that stalls in an interview.
The reflex is to generate everything and filter. There are 2^(2n) strings of length 2n over the alphabet {'(', ')'}, so you produce all of them, run a validity check on each, and keep the ones that pass. It works. It also does a staggering amount of pointless work: for n = 5 you build 1,024 candidates to keep 42 of them. The interviewer nods, then asks the question they were always going to ask, which is whether you can avoid building the strings you were only going to throw away.
Build only what can still be valid
The fix is to never place a character that breaks the string. Track two counts as you build: how many opening brackets you’ve used, and how many closing ones. Two rules keep every partial string on a path toward a valid answer. You can add '(' as long as you haven’t used all n of them. You can add ')' only when there’s an unmatched '(' waiting for it, meaning the number of closing brackets so far is strictly less than the number of opening ones.
That second rule is the whole trick. It guarantees you never write a ')' with nothing to close, so you never produce a prefix like ()) that can’t be repaired no matter what you append. When both counts reach n, the string is complete and valid, and you record it.
def generate_parenthesis(n):
result = []
def build(current, open_used, close_used):
if len(current) == 2 * n:
result.append(current)
return
if open_used < n:
build(current + "(", open_used + 1, close_used)
if close_used < open_used:
build(current + ")", open_used, close_used + 1)
build("", 0, 0)
return result
No explicit validity check appears anywhere. The constraints on the two recursive calls do the checking for you, before a bad character is ever placed. That's the split between backtracking and brute force. Brute force validates after the fact; backtracking refuses to walk down a dead branch in the first place.
Why the complexity is a Catalan number, not 2^(2n)
People freeze on the complexity here, and the answer is genuinely a bit subtle. The number of valid strings for n pairs is the nth Catalan number, C_n = (2n choose n) / (n + 1). Each valid string takes O(n) work to assemble and copy, so total time is O(n · C_n), usually written as O(4^n / √n) because the Catalan numbers grow like 4^n / n^1.5. That's far smaller than the 2^(2n) = 4^n candidates the brute force churns through, and the gap between them is exactly the fraction of strings that turn out to be valid.
Knowing the Catalan sequence by sight helps you sanity-check your output in the room. If your code returns 15 strings for n = 4 instead of 14, you have an off-by-one somewhere and you'll catch it before the interviewer does.
| Pairs of parentheses (n) | Valid strings returned (Catalan number Cₙ) | Brute-force candidates checked (2^(2n)) |
|---|---|---|
| 1 | 1 | 4 |
| 2 | 2 | 16 |
| 3 | 5 | 64 |
| 4 | 14 | 256 |
| 5 | 42 | 1,024 |
| 6 | 132 | 4,096 |
| 10 | 16,796 | 1,048,576 |
The pattern under the problem
Generate Parentheses is the cleanest teaching case for constrained backtracking, a recursion where the choices at each step are limited by a rule about the partial solution so far. The shape shows up everywhere once you can see it. Letter combinations of a phone number, subsets, permutations, combination sum, N-Queens. Each one builds a candidate incrementally and cuts off branches that can't lead anywhere.
This is a different problem from Valid Parentheses (LeetCode 20), which people conflate because the names rhyme. That one hands you a finished string and asks whether it's balanced, and you answer it with a stack in a single pass. Generate Parentheses produces strings rather than checking them, and a stack buys you nothing. Reaching for a stack when you should be recursing is a common way to burn five minutes going nowhere.
The follow-ups interviewers actually reach for
Once the base solution is on the board, the questions branch in a few predictable directions.
The most common one is counting instead of listing. If all they want is how many valid strings exist for n pairs, generating them is wasteful, since the answer is just C_n and you can compute it with the closed form or a small dynamic-programming recurrence in O(n). Interviewers use this to check whether you notice that enumeration and counting are different problems with wildly different costs.
A harder variant swaps in multiple bracket types, say parentheses, square brackets, and braces, all of which have to nest correctly. The two-counter rule no longer covers it, because ) can only close (, never [. Now you carry the actual stack of open brackets inside the recursion so you know which closer is legal next, and the counting trick generalizes into tracking that stack.
Some interviewers ask for the iterative version to see whether you understand what the call stack was doing for you. You can reproduce the recursion with an explicit stack or queue of partial states, each holding the string so far plus its open and close counts. It's rarely cleaner than the recursive version, but writing it shows you're reasoning about the mechanism rather than reciting a memorized template.
The memory question comes up a lot too. Recursion depth is 2n, so the call stack costs O(n). The output itself holds C_n strings of length 2n, which dwarfs the stack. If someone asks you to cut space without changing what gets returned, the right answer is that you can't: the result set is the floor, and there's nothing to shave beneath it.
Where people actually lose points
The bug I see most is the closing-bracket condition written as close_used < n instead of close_used < open_used. The first version happily builds )( and then fails the length check without ever catching the imbalance, so you get wrong output and a puzzled candidate staring at it. The count you compare against is the number of opens placed so far, not the target n.
The other frequent miss is string handling in languages where concatenation is costly. In Python, current + "(" allocates a new string every call, which is fine at interview scale but worth a spoken aside. In Java or C++, the idiomatic move is a single mutable StringBuilder or char[] that you append to before the recursive call and truncate after, the real "backtrack" step that gives the technique its name. If you write the mutable version, say out loud that you're undoing the choice on the way back up, because that sentence is half of what the round is testing.
Talk through the two rules before you write them, put the tiny n = 2 case on the board to show (()) and ()() falling out of it, and the whole thing takes a couple of minutes. The problem rewards understanding the state you're tracking far more than it rewards clever code, which is exactly why it keeps showing up.
Drill the patterns next:
