Learning Outcome
After this lesson, you should be able to prune invalid prefixes before they are generated.
Problem Statement
Given n pairs of parentheses, generate all combinations of well-formed parentheses.
| Input | Output | Why |
|---|---|---|
n = 3 | ["((()))","(()())","(())()","()(())","()()()"] | Only strings where every prefix has close count <= open count are valid. |
Brute Force Approach
Generate every string of length 2n made of ( and ), then filter invalid strings. This creates many impossible states.
Optimized Approach
Backtrack only through valid states: add ( while open < n, and add ) only while close < open.
Exact Pseudocode
answer = []
dfs(path, open, close):
if length(path) == 2 * n:
answer.add(path)
return
if open < n:
dfs(path + "(", open + 1, close)
if close < open:
dfs(path + ")", open, close + 1)
return answerReference Code
class Solution:
def generateParenthesis(self, n):
answer = []
def dfs(path, open_count, close_count):
if len(path) == 2 * n:
answer.append(path)
return
if open_count < n:
dfs(path + "(", open_count + 1, close_count)
if close_count < open_count:
dfs(path + ")", open_count, close_count + 1)
dfs("", 0, 0)
return answerSample Dry Run
| Step | State | Result |
|---|---|---|
| Start | path="", open=0, close=0 | Only "(" is allowed |
| path="(" | open=1, close=0 | Can add "(" or ")" |
| Invalid prefix blocked | close can never exceed open | No path starts with ")" |
| Length 6 | Valid path copied | Answer receives one string |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(Cn) | The number of valid strings is the nth Catalan number. |
| Space | O(n) | The recursion path length is at most 2n. |
Edge Cases
- n = 1 returns ["()"].
- Never allow close count to exceed open count.
- Stop when path length reaches 2n.
Interview Checklist
- Track open and close counts separately.
- Prune invalid prefixes early.
- Add a complete path only at length 2n.
FAQs
Why is close < open required?
A closing parenthesis is valid only if there is an unmatched opening parenthesis.
Why not generate all strings first?
Most generated strings would be invalid, so pruning saves work and is clearer.
What is the core pattern?
Valid-state backtracking.