Appearance
4.8.4 — Generate Parentheses
LeetCode 22 · Medium · ★ Blind 75
The problem
You are given a number n. Return every string made of n opening brackets ( and n closing brackets ) that is well-formed. Well-formed means every ( is closed by a later ), and no ) appears without an open ( before it to close.
n = 1 → ["()"]
n = 3 → ["((()))", "(()())", "(())()", "()(())", "()()()"]n is between 1 and 8.
That small limit is a hint. When n is this small, the answer is allowed to grow very fast with n, because the answer is a list of every possibility.
What the problem is really asking
Picture building the string one character at a time, left to right. At each step you choose ( or ). Some choices lead to a valid string. Others are doomed. For example, a string that starts with ) can never be fixed.
So the real question is: at each step, which choices are still safe, so that we only ever build valid strings?
There is a simple test. Read a string left to right and count opens and closes as you go. It is well-formed exactly when:
- The count of closes never goes above the count of opens at any point, and
- At the end, both counts equal
n.
Think of people entering and leaving a room. ( is someone walking in, and ) is someone walking out. The room holds at most n people in total over the day. And nobody can walk out of an empty room. If you obey those two rules at the door, every day you record is valid.
The brute force, and where it wastes work
Make every string of length 2n out of ( and ), then keep only the valid ones.
python
from itertools import product
def generateParenthesis(n):
def valid(s):
balance = 0
for c in s:
balance += 1 if c == '(' else -1
if balance < 0: # a close with nothing open
return False
return balance == 0
return [''.join(p) for p in product('()', repeat=2 * n) if valid(p)]There are 2^{2n} such strings. For n = 8 that is 65,536, and only 1,430 of them are valid. Each costs O(n) to check.
The waste in one sentence: it builds strings like "))))((((" all the way to the end, even though the very first character already doomed them.
The idea
Build the string step by step, and only ever make a choice that keeps it valid. There are two choices, each with a simple rule.
- Add
(if fewer thannopens have been used. - Add
)if fewer closes than opens have been used. That means there is an open bracket waiting to be closed.
If you follow these rules at every step, every complete string you build is valid. You never need to check anything at the end.
This way of searching has a name: backtracking. You build a partial answer, try each allowed next step, and after exploring a step you undo it so you can try the next one. This is the first backtracking problem in the book. Every problem in 4.18 uses the same four parts:
- A finish line. When the answer is complete, record it.
- The choices. Here, add
(or add). - The rule in front of each choice. This is what stops you building doomed answers.
- The undo. After exploring a choice, take it back.
The solution
python
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
result = [] # (1)
current = [] # (2)
def build(open_count: int, close_count: int): # (3)
if len(current) == 2 * n: # (4)
result.append(''.join(current))
return
if open_count < n: # (5)
current.append('(')
build(open_count + 1, close_count)
current.pop() # (6)
if close_count < open_count: # (7)
current.append(')')
build(open_count, close_count + 1)
current.pop()
build(0, 0) # (8)
return resultts
function generateParenthesis(n: number): string[] {
const result: string[] = []; // (1)
const current: string[] = []; // (2)
function build(open: number, close: number): void { // (3)
if (current.length === 2 * n) { // (4)
result.push(current.join(''));
return;
}
if (open < n) { // (5)
current.push('(');
build(open + 1, close);
current.pop(); // (6)
}
if (close < open) { // (7)
current.push(')');
build(open, close + 1);
current.pop();
}
}
build(0, 0); // (8)
return result;
}Line by line
(1) result collects every finished string.
(2) current is the string being built right now, kept as a list of characters. A list is used because adding or removing the last character of a list takes constant time.
(3) The build function. It is recursive, meaning it calls itself. Each call represents one point in the building process. It is told how many opens and closes have been used so far.
(4) The finish line. A valid string has n opens and n closes, so its length is 2n. When current reaches that length, we join the characters into one string, save it, and return to go back to the previous step.
(5) Choice one: add (. Only allowed if we have used fewer than n opens. We add it, then call build to keep going from this new point, with one more open used.
(6) The undo. When that call returns, every string that starts with our current characters plus ( has been built. Now we remove the (, so current is exactly as it was before line (5). That lets choice two start from a clean state.
Do not skip the undo. Without it, current would keep growing across different branches, and every string after the first would be wrong. The rule is simple: whatever you add before the call, remove after it.
(7) Choice two: add ). Only allowed if more opens than closes have been used, meaning some ( is still waiting to be closed. Same pattern: add, go deeper, undo.
(8) Start with nothing used.
Why one shared list, instead of passing strings?
You could write build(current + '(') and skip the undo, because each call would get its own new string. That is shorter and harder to get wrong. But it builds a brand-new string at every step, and copying a string of length up to 2n costs O(n) each time. The shared list with an undo avoids that copying. It is the habit worth building now, because the harder backtracking problems cannot afford the copies.
Trace
Here is the full search for n = 2. Each line is one call of build, indented by how deep it is.
build(0,0) current = ""
add "(" → build(1,0) current = "("
add "(" → build(2,0) current = "(("
open is 2, so no more "("
add ")" → build(2,1) current = "(()"
add ")" → build(2,2) current = "(())" length 4 → save "(())"
undo ")"
undo ")"
undo "(" current = "("
add ")" → build(1,1) current = "()"
add "(" → build(2,1) current = "()("
add ")" → build(2,2) current = "()()" length 4 → save "()()"
undo ")"
undo "("
close is not less than open, so no ")"
undo ")"
undo "("
close (0) is not less than open (0), so no ")" at the very startThe result is ["(())", "()()"]. Notice that no string ever starts with ). The rule in line (7) blocked it at the very first step, so that whole branch was never built.
Complexity, derived
How many answers are there? The number of valid strings with n pairs is called the n-th Catalan number, written C_n:
C_n = \frac{1}{n+1}\binom{2n}{n}
Read \binom{2n}{n} as "2n choose n". It is the number of ways to pick n positions out of 2n, which here means choosing where the opens go. Dividing by n + 1 keeps only the arrangements that are valid. For n = 3 this gives \frac{1}{4} \times 20 = 5, which matches the example. For n = 8 it is 1,430.
Time. Because of the rules, every partial string the code builds can be finished into a valid one. So the work is spread over the valid answers, and each finished answer costs O(n) to join into a string. The total is about O(n \cdot C_n). C_n grows roughly like 4^n divided by n^{1.5}, so this is exponential.
That sounds bad, but there is no way around it. The answer itself is a list of C_n strings, each of length 2n. Any method must at least write them all down. When a problem asks for every possibility, the size of the answer sets the speed limit.
Space. Not counting the answer list, the deepest the recursion goes is 2n calls, and current holds at most 2n characters. So the extra memory is O(n).
Edge cases
n = 1. The only answer is"()".- The first character. It is always
(, because line (7) cannot run when no opens have been used. - The last character. It is always
), because by then allnopens are used.
Variations you will meet
Every backtracking problem in 4.18 is these four parts with different choices and rules.
- Subsets. The choice is "take this item or skip it". There is no rule.
- Permutations. The choice is "which unused item goes next". The rule is "unused".
- N-Queens. The choice is which column to place a queen in. The rule is "no two queens attack each other".
- Word Search. The choice is which neighbouring cell to step to. The rule is "the letter matches and the cell is not already used".
Where the rule sits decides everything. Checking the rule at each step cuts off whole branches early. Checking it only on finished answers is just the brute force written as recursion.
What the interviewer will push on
"Why is close < open the right rule?" A string is well-formed exactly when closes never get ahead of opens at any point. Enforcing it at each step makes every finished string valid.
"What is the time complexity?" Catalan-many answers, O(n) each. Then say that the size of the answer sets the limit.
"Why not build everything and filter?" 2^{2n} strings instead of C_n. For n = 8 that is 65,536 against 1,430, about 45 times more work, and the gap grows fast.
"Why do you need the undo?" current is shared by every branch, so it must be put back before trying the next choice.
"Can you do it without recursion?" Yes, with your own stack of partial strings. It is messier. Recursion fits naturally, because the search is shaped like a tree.
One thing to volunteer: name the four parts of backtracking as you write them: finish line, choices, rule, undo. That 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 group worth studying.