Appearance
4.8.4 — Generate Parentheses
LeetCode 22 · Medium · ★ Blind 75
The problem
Given n pairs of brackets, return every well-formed combination.
n = 3 → ["((()))", "(()())", "(())()", "()(())", "()()()"]
n = 1 → ["()"]n is between 1 and 8.
The pattern
Despite sitting in the stack group, this is not a stack problem. It is the first backtracking problem in the book — build a partial answer, extend it in every legal way, and undo each choice on the way back out.
The naive approach generates all 2^{2n} strings of brackets and filters the valid ones. For n = 8 that is 65,536 strings, most of them invalid. Wasteful, and it misses the point.
Instead, never build an invalid string in the first place. At each position you have at most two choices, and each has a simple condition:
- Add
(— allowed while you have used fewer thannopen brackets. - Add
)— allowed while the number of closes is strictly less than the number of opens.
That second rule is the whole problem. A string is well-formed exactly when, reading left to right, closes never overtake opens, and the two totals end equal. Enforce it at every step and every string you produce is valid by construction.
The solution
python
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
result = []
current = []
def build(open_count: int, close_count: int):
if len(current) == 2 * n: # a complete string
result.append(''.join(current))
return
if open_count < n: # can still open
current.append('(')
build(open_count + 1, close_count)
current.pop() # undo
if close_count < open_count: # can still close
current.append(')')
build(open_count, close_count + 1)
current.pop() # undo
build(0, 0)
return resultts
function generateParenthesis(n: number): string[] {
const result: string[] = [];
const current: string[] = [];
function build(open: number, close: number): void {
if (current.length === 2 * n) {
result.push(current.join(''));
return;
}
if (open < n) {
current.push('(');
build(open + 1, close);
current.pop();
}
if (close < open) {
current.push(')');
build(open, close + 1);
current.pop();
}
}
build(0, 0);
return result;
}The four parts of backtracking are all here, and every problem in 4.18 has the same four:
- A base case — the string is
2nlong, so record it and stop. - The choices — add
(or add). - The constraint — the
ifin front of each choice, which is what makes this efficient rather than brute force. - The undo —
current.pop()after each recursive call, restoring the state so the next choice starts clean.
Do not skip the undo. Without it, current keeps growing across branches and every result is wrong. The rule is: whatever you add before recursing, remove after.
Why one shared list instead of passing strings around? You could write build(current + '(') and skip the undo entirely, since strings are immutable and each call gets its own copy. That is shorter and easier to get right. It also allocates a new string at every node of the recursion tree, which is O(n) work per node. The shared list with an explicit undo is the version that scales, and it is the habit worth building because the harder backtracking problems cannot afford the copies.
''.join(current) at the base case is the only place a string is built.
The recursion tree for n = 2
""
/
"(" open=1
/ \
"((" "()" open=2 / close=1
| |
"(()" "()(" close=1 / open=2
| |
"(())" "()()" ← both completeNotice what is missing: there is no branch starting with ), because close < open is false at the root. The constraint pruned it before it was ever built.
Complexity
The number of valid strings for n pairs is the n-th Catalan number:
C_n = \frac{1}{n+1}\binom{2n}{n}
which grows roughly like 4^n / n^{1.5}. For n = 8 that is 1,430 strings.
Each result costs O(n) to assemble, so the total is O(n \cdot C_n).
The honest way to say this in an interview: "the output is exponential in size, so the algorithm must be at least exponential — but the pruning means we only ever visit valid partial strings, never invalid ones." That sentence is worth more than reciting the Catalan formula. It also names the general truth about enumeration problems: when the answer is a list of every possibility, the complexity is dominated by the size of the output, not by cleverness.
Where this goes next
This is the template for the whole of 4.18. Every problem there is these four parts with different choices and different constraints:
- Subsets — the choice is "include this element or not", and there is no constraint.
- Permutations — the choice is "which unused element comes next", and the constraint is "unused".
- N-Queens — the choice is which column, and the constraint is no shared row, column or diagonal.
- Word Search — the choice is which neighbour to step to, and the constraint is that the letter matches and the cell is unvisited.
Where the constraint sits decides everything. Checking validity as you make each choice prunes whole subtrees. Checking it only on complete answers is brute force wearing a recursion costume.
What the interviewer will push on
"Why is close < open the right condition?" Because a string is well-formed exactly when closes never overtake opens at any prefix. Enforcing it per step makes every generated string valid.
"What is the complexity?" Catalan-many results, O(n) each. Then the sentence about output size dominating.
"Why not generate everything and filter?" 2^{2n} strings instead of C_n — about 45 times more work at n = 8, and the gap widens fast.
"Why the undo?" The list is shared across branches, so state must be restored before trying the next choice.
"Could you do it iteratively?" Yes, with an explicit stack of partial states, or by building n from n−1 results. Both are messier. Recursion is the natural fit because the problem is naturally a tree.
One thing to volunteer: name the four parts of backtracking as you write them. Choices, constraint, recurse, undo. That framing tells the interviewer you have a method that will work on the next backtracking problem too.
Next: 4.8.5 Daily Temperatures — the first monotonic stack, which is the idea that makes this whole group worth studying.