265. Generate Parentheses
🔗 LeetCode Problem: 22. Generate Parentheses
📊 Difficulty: Medium
🏷️ Topics: Stack, Backtracking, String, Dynamic Programming
Problem Statement
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]
Example 3:
Input: n = 2
Output: ["(())","()()"]
Constraints:
- 1 <= n <= 8
🌟 ELI5: The Simple Idea!
Think of building valid parentheses step by step:
n = 2 means we have 2 opening '(' and 2 closing ')'
Valid combinations:
"(())" ✓
"()()" ✓
Invalid combinations:
")()(" ✗ - Starts with closing
"(((" ✗ - Not all closed
"((()" ✗ - Too many opening
Rules to stay valid:
1. Can't use more '(' than we have (max n)
2. Can't use more ')' than we have (max n)
3. Can't close more than we've opened
The Building Process:
Start: ""
Can add '(' (have 2 left)
→ "("
From "(":
Can add '(' (have 1 left)
→ "(("
Can add ')' (opened 1, can close)
→ "()"
Continue until all valid combinations found!
🎨 Visual Understanding
Decision Tree for n=2
""
↓
"("
↙ ↘
"((" "()"
↓ ↙ ↘
"(()" "()(" "()" ✗ (can't add more)
↓ ↓
"(())" "()()"
✓ ✓
Valid paths lead to complete strings with 2n characters!
Building Process
n = 3 (3 pairs)
Goal: Use exactly 3 '(' and 3 ')'
Start: ""
open = 0, close = 0
Step 1: Add '('
"("
open = 1, close = 0
Step 2: Can add '(' or ')'
Branch 1: "((" (open=2, close=0)
Branch 2: "()" (open=1, close=1)
Step 3: Continue branching...
Eventually get all valid combinations:
"((()))", "(()())", "(())()", "()(())", "()()()"
🎯 Approach 1: Backtracking (Recursion) ⭐⭐
The Most Common Solution
Algorithm:
Use backtracking with tracking:
- How many '(' used (open)
- How many ')' used (close)
- Current string being built
Rules:
1. Can add '(' if open < n
2. Can add ')' if close < open
3. If open == close == n → valid combination!
Implementation
import java.util.*;
/**
* Backtracking approach
* Time: O(4^n / √n) - Catalan number
* Space: O(n) - Recursion depth
*/
class Solution {
private List<String> result;
public List<String> generateParenthesis(int n) {
result = new ArrayList<>();
backtrack("", 0, 0, n);
return result;
}
private void backtrack(String current, int open, int close, int max) {
// Base case: completed valid combination
if (current.length() == max * 2) {
result.add(current);
return;
}
// Add opening parenthesis
if (open < max) {
backtrack(current + "(", open + 1, close, max);
}
// Add closing parenthesis
if (close < open) {
backtrack(current + ")", open, close + 1, max);
}
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.generateParenthesis(3));
System.out.println(sol.generateParenthesis(1));
}
}
⏰ Time: O(4^n / √n) - Catalan number C_n
💾 Space: O(n) - Maximum recursion depth
Using StringBuilder (More Efficient)
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
backtrack(result, new StringBuilder(), 0, 0, n);
return result;
}
private void backtrack(List<String> result, StringBuilder sb,
int open, int close, int max) {
if (sb.length() == max * 2) {
result.add(sb.toString());
return;
}
if (open < max) {
sb.append('(');
backtrack(result, sb, open + 1, close, max);
sb.deleteCharAt(sb.length() - 1); // Backtrack
}
if (close < open) {
sb.append(')');
backtrack(result, sb, open, close + 1, max);
sb.deleteCharAt(sb.length() - 1); // Backtrack
}
}
More efficient - reuses StringBuilder!
🔍 Super Detailed Dry Run
Example: n = 2
Goal: Generate all valid combinations of 2 pairs
═══════════════════════════════════════════════════════════════
Backtrack Call Tree
═══════════════════════════════════════════════════════════════
Call 1: backtrack("", open=0, close=0, max=2)
Length: 0 < 4 → Continue
Can add '('? open(0) < max(2) → Yes
→ Recurse: backtrack("(", 1, 0, 2)
═══════════════════════════════════════════════════════════════
Call 2: backtrack("(", open=1, close=0, max=2)
Length: 1 < 4 → Continue
Can add '('? open(1) < max(2) → Yes
→ Recurse: backtrack("((", 2, 0, 2)
Can add ')'? close(0) < open(1) → Yes
→ Recurse: backtrack("()", 1, 1, 2)
═══════════════════════════════════════════════════════════════
Call 3: backtrack("((", open=2, close=0, max=2)
Length: 2 < 4 → Continue
Can add '('? open(2) < max(2) → No
Can add ')'? close(0) < open(2) → Yes
→ Recurse: backtrack("(()", 2, 1, 2)
═══════════════════════════════════════════════════════════════
Call 4: backtrack("(()", open=2, close=1, max=2)
Length: 3 < 4 → Continue
Can add '('? open(2) < max(2) → No
Can add ')'? close(1) < open(2) → Yes
→ Recurse: backtrack("(())", 2, 2, 2)
═══════════════════════════════════════════════════════════════
Call 5: backtrack("(())", open=2, close=2, max=2)
Length: 4 == 4 → Base case!
Add "(())" to result
Return
Result: ["(())"]
═══════════════════════════════════════════════════════════════
[Back to Call 4]
Finished exploring ')'
Return
[Back to Call 3]
Finished exploring ')'
Return
[Back to Call 2]
Finished exploring '(' path
Now explore ')' path:
═══════════════════════════════════════════════════════════════
Call 6: backtrack("()", open=1, close=1, max=2)
Length: 2 < 4 → Continue
Can add '('? open(1) < max(2) → Yes
→ Recurse: backtrack("()(", 2, 1, 2)
Can add ')'? close(1) < open(1) → No
═══════════════════════════════════════════════════════════════
Call 7: backtrack("()(", open=2, close=1, max=2)
Length: 3 < 4 → Continue
Can add '('? open(2) < max(2) → No
Can add ')'? close(1) < open(2) → Yes
→ Recurse: backtrack("()()", 2, 2, 2)
═══════════════════════════════════════════════════════════════
Call 8: backtrack("()()", open=2, close=2, max=2)
Length: 4 == 4 → Base case!
Add "()()" to result
Return
Result: ["(())", "()()"]
═══════════════════════════════════════════════════════════════
[Back to Call 7, 6, 2, 1]
All paths explored
Final Result: ["(())", "()()"]
Visual Decision Tree:
("", 0, 0)
|
("(", 1, 0)
/ \
("((", 2, 0) ("()", 1, 1)
| |
("(()", 2, 1) ("()(", 2, 1)
| |
"(())" ✓ "()()" ✓
🎯 Approach 2: Iterative (Using Stack) ⭐
Alternative Solution
Algorithm:
Use a stack to store states: (current_string, open_count, close_count)
Process like BFS/DFS until all combinations found
Implementation
import java.util.*;
class Solution {
// State class to track current combination
static class State {
String str;
int open;
int close;
State(String str, int open, int close) {
this.str = str;
this.open = open;
this.close = close;
}
}
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
Stack<State> stack = new Stack<>();
stack.push(new State("", 0, 0));
while (!stack.isEmpty()) {
State current = stack.pop();
// If we've used all parentheses
if (current.open == n && current.close == n) {
result.add(current.str);
continue;
}
// Try adding '('
if (current.open < n) {
stack.push(new State(
current.str + "(",
current.open + 1,
current.close
));
}
// Try adding ')'
if (current.close < current.open) {
stack.push(new State(
current.str + ")",
current.open,
current.close + 1
));
}
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.generateParenthesis(2));
}
}
⏰ Time: O(4^n / √n)
💾 Space: O(4^n / √n) - Stack can hold many states
🔍 Detailed Dry Run (Iterative)
n = 2
stack = [("", 0, 0)]
═══════════════════════════════════════════════════════════════
Iteration 1:
Pop: ("", 0, 0)
Not complete (0 != 2)
Push: ("(", 1, 0)
Stack: [("(", 1, 0)]
═══════════════════════════════════════════════════════════════
Iteration 2:
Pop: ("(", 1, 0)
Not complete
Can add '('? 1 < 2 → Yes, push ("((", 2, 0)
Can add ')'? 0 < 1 → Yes, push ("()", 1, 1)
Stack: [("((", 2, 0), ("()", 1, 1)]
═══════════════════════════════════════════════════════════════
Iteration 3:
Pop: ("()", 1, 1)
Not complete
Can add '('? 1 < 2 → Yes, push ("()(", 2, 1)
Can add ')'? 1 < 1 → No
Stack: [("((", 2, 0), ("()(", 2, 1)]
═══════════════════════════════════════════════════════════════
Iteration 4:
Pop: ("()(", 2, 1)
Not complete
Can add '('? 2 < 2 → No
Can add ')'? 1 < 2 → Yes, push ("()()", 2, 2)
Stack: [("((", 2, 0), ("()()", 2, 2)]
═══════════════════════════════════════════════════════════════
Iteration 5:
Pop: ("()()", 2, 2)
Complete! open=2, close=2
Add "()()" to result ✓
Result: ["()()"]
Stack: [("((", 2, 0)]
═══════════════════════════════════════════════════════════════
Iteration 6:
Pop: ("((", 2, 0)
Not complete
Can add '('? 2 < 2 → No
Can add ')'? 0 < 2 → Yes, push ("(()", 2, 1)
Stack: [("(()", 2, 1)]
═══════════════════════════════════════════════════════════════
Iteration 7:
Pop: ("(()", 2, 1)
Not complete
Can add '('? 2 < 2 → No
Can add ')'? 1 < 2 → Yes, push ("(())", 2, 2)
Stack: [("(())", 2, 2)]
═══════════════════════════════════════════════════════════════
Iteration 8:
Pop: ("(())", 2, 2)
Complete! open=2, close=2
Add "(())" to result ✓
Result: ["()()", "(())"]
Stack: []
═══════════════════════════════════════════════════════════════
Stack empty → Done!
Final Result: ["()()", "(())"]
⚠️ Common Mistakes
Mistake 1: Wrong condition for adding ')'
// ❌ WRONG - Allows more ')' than '('
if (close < max) {
backtrack(result, current + ")", open, close + 1, max);
}
// Generates: "))((" ✗
// ✓ CORRECT - Ensures ')' doesn't exceed '('
if (close < open) {
backtrack(result, current + ")", open, close + 1, max);
}
Mistake 2: Wrong base case
// ❌ WRONG - Only checks one counter
if (open == max) {
result.add(current);
return;
}
// Generates incomplete: "(((" ✗
// ✓ CORRECT - Check both counters OR length
if (current.length() == max * 2) {
result.add(current);
return;
}
// OR
if (open == max && close == max) {
result.add(current);
return;
}
Mistake 3: Not checking open < n
// ❌ WRONG - No limit on '('
backtrack(result, current + "(", open + 1, close, max);
// ✓ CORRECT - Check first
if (open < max) {
backtrack(result, current + "(", open + 1, close, max);
}
Mistake 4: Forgetting to backtrack with StringBuilder
// ❌ WRONG - Doesn't undo!
sb.append('(');
backtrack(result, sb, open + 1, close, max);
// sb still has '(' for next iteration!
// ✓ CORRECT - Undo after recursion
sb.append('(');
backtrack(result, sb, open + 1, close, max);
sb.deleteCharAt(sb.length() - 1); // Backtrack!
Mistake 5: Using mutable list incorrectly
// ❌ WRONG - Modifying shared list
List<Character> current = new ArrayList<>();
// Pass same list to all recursive calls
// All branches modify same list!
// ✓ CORRECT - Use String or copy list
String current = "";
// OR create new list for each branch
🎯 Pattern Recognition
Problem Type: Generate All Valid Combinations
Core Pattern: Backtracking + Stack Validation
When to Apply:
✓ Generate all valid sequences
✓ Build valid structures recursively
✓ Explore all possibilities with constraints
✓ Combination generation
Recognition Keywords:
- "generate all"
- "well-formed"
- "valid combinations"
- "parentheses"
- "n pairs"
Similar Problems:
- Valid Parentheses (LC 20) - Validation (easier)
- Different Ways to Add Parentheses (LC 241)
- Remove Invalid Parentheses (LC 301) - Hard
- Longest Valid Parentheses (LC 32) - Hard
Key Components:
┌────────────────────────────────────────────┐
│ Backtracking: Explore all valid paths │
│ Rule 1: open < n (can add '(') │
│ Rule 2: close < open (can add ')') │
│ Base case: length == 2n │
│ Optimization: StringBuilder reuse │
│ Time: O(4^n/√n), Space: O(n) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "This is a backtracking problem"
Step 2: "I need to generate all valid combinations"
Step 3: "I'll use two counters to track usage"
Key Points to Mention:
- Backtracking explores all valid paths
- Two rules: can add '(' if open < n
can add ')' if close < open
- Base case: length equals 2n
- Can optimize with StringBuilder reuse
- Time: Catalan number O(4^n/√n)
Walk Through Example:
"For n=2:
Start with empty string
Add '(' → '('
Can add '(' → '((' → '(()' → '(())' ✓
Can add ')' → '()' → '()(' → '()()' ✓
Both valid combinations found"
Why Backtracking:
"Need to explore all possibilities.
At each step, try adding '(' or ')'.
Rules prevent invalid combinations.
Backtracking naturally tries all valid paths."
Complexity:
"Time is O(4^n/√n) - Catalan number.
This is optimal for generating all combinations.
Space is O(n) for recursion depth.
Can't improve asymptotically."
Edge Cases to Mention:
✓ n = 1 → "()"
✓ n = 2 → "(())", "()()"
✓ n = 3 → 5 combinations
✓ Order doesn't matter in result
📝 Quick Revision Notes
🎯 Core Concept:
Generate Parentheses: Use backtracking to build all valid combinations. Track open and close counts. Add '(' if open < n. Add ')' if close < open. Base case: length == 2n. Time: Catalan number O(4^n/√n).
⚡ Quick Implementation:
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Solution {
private static class State {
String str;
int open;
int close;
public State(String str, int open, int close) {
this.str = str;
this.open = open;
this.close = close;
}
}
public List<String> generateParenthesis(int n) {
// return recursive(n);
return iterative(n);
}
private List<String> iterative(int n) {
List<String> res = new ArrayList<>();
StringBuilder sb = new StringBuilder();
// step 1: same as before except that we maintain state in stack
Stack<State> stack = new Stack<>();
stack.push(new State("", 0, 0));
// step 2: loop till stack becomes empty
while (!stack.isEmpty()) {
State curr = stack.pop();
String str = curr.str;
int open = curr.open;
int close = curr.close;
// step 4: base case
if (open == n && close == n) {
res.add(curr.str);
continue;
}
// step 3: same as recursive.
// we should not use sb as its diff from recursion
// as we keep on processing that sb in later calls.
// Here its not like that.
if (open < n) {
stack.push(new State(str.concat("("), open + 1, close));
}
if (close < open) {
stack.push(new State(str.concat(")"), open, close + 1));
}
}
return res;
}
private List<String> recursive(int n) {
List<String> res = new ArrayList<>();
recursiveUtil(0, 0, new StringBuilder(), n, res);
return res;
}
private void recursiveUtil(int open, int close, StringBuilder sb, int n, List<String> res) {
// step 5: base case
if (open == n && close == n) {
res.add(sb.toString());
}
// step 1: check if we can add open paranthesis
if (open < n) {
// step 2: if we can add, add it and go to next possible
sb.append("(");
recursiveUtil(open + 1, close, sb, n, res);
// step 3: remove the added paranthesis and check for next possible
sb.deleteCharAt(sb.length() - 1);
}
// step 4: check if we can add close paranthesis
if (close < open) {
sb.append(")");
recursiveUtil(open, close + 1, sb, n, res);
sb.deleteCharAt(sb.length() - 1);
}
}
public static void main(String[] args) {
Solution s = new Solution();
// .equals(List.of("((()))", "(()())", "(())()", "()(())", "()()()"))
System.out
.println(s.generateParenthesis(3));
}
}
🔑 Key Insights:
- Pattern: Backtracking + Validation
- Rule 1: Can add '(' if open < n
- Rule 2: Can add ')' if close < open
- Base case: length == 2n
- Guarantees: Always valid, all combinations
- Time: O(4^n/√n), Space: O(n) ✓
🎪 Memory Aid:
"Open before close, count both, explore all!"
"Add ( if can, add ) if have (, done at 2n!" ✨
⚠️ Two Critical Rules:
Rule 1: if (open < max)
→ Can still add opening bracket
→ Haven't used all n yet
Rule 2: if (close < open)
→ Can add closing bracket
→ Have unmatched opening to close
Without Rule 2:
Could generate ")(" ✗
Without Rule 1:
Could generate "(((" ✗
Both rules together → Always valid!
🧪 Edge Cases
Case 1: n = 1
Input: n = 1
Output: ["()"]
Only one valid combination
Case 2: n = 2
Input: n = 2
Output: ["(())", "()()"]
Two valid combinations
Case 3: n = 3
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Five valid combinations (Catalan number C_3 = 5)
All handled correctly! ✓
🎓 Complexity Analysis
Time Complexity: O(4^n / √n)
This is the n-th Catalan number!
Catalan number C_n = (2n)! / ((n+1)! * n!)
Asymptotic: O(4^n / (n^(3/2)))
Why?
- Each valid combination has 2n characters
- Number of valid combinations is C_n
- Total characters generated: C_n × 2n
For small n:
n=1: 1 combination
n=2: 2 combinations
n=3: 5 combinations
n=4: 14 combinations
n=5: 42 combinations
Space Complexity: O(n)
Recursion stack depth:
Maximum depth = 2n (building string of length 2n)
Each call: O(1) space (just variables)
Total: O(n)
Result storage not counted in space complexity
(output doesn't count towards auxiliary space)
📚 Related Problems
Same Core Pattern: - Letter Combinations of Phone Number (LC 17) - Backtracking - Permutations (LC 46) - Backtracking - Subsets (LC 78) - Backtracking
Parentheses Family: - Valid Parentheses (LC 20) - Validation (easier) - Minimum Add to Make Valid (LC 921) - Remove Invalid Parentheses (LC 301) - Hard - Longest Valid Parentheses (LC 32) - Hard
Happy practicing! 🎯
Note: This is a MEDIUM backtracking problem! Master this and you understand: (1) backtracking fundamentals, (2) constraint-based generation, (3) Catalan numbers, (4) pruning invalid paths. This pattern extends to many combination generation problems. Very common at Amazon, Meta, Google! 💪✨