#22
Generate Parentheses
Medium Backtracking with counts
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return every valid string of n pairs of parentheses.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: all valid strings with n pairs of brackets.
Why this works: add '(' while you have some left; add ')' only if it closes something open. Only valid strings get built.
Example: n = 2
"((" → "(())""()" → "()()"
✦Hints open one at a time
You may add '(' while you've used fewer than n.
You may add ')' only while closes < opens.
↗Approach
Recurse with counts of open and close brackets used. These two rules generate only valid strings, so no checking is needed at the end.
</>Solution (Java)
import java.util.*;
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
build(n, 0, 0, new StringBuilder(), res);
return res;
}
private void build(int n, int open, int close, StringBuilder sb, List<String> res) {
if (sb.length() == 2 * n) {
res.add(sb.toString());
return;
}
if (open < n) {
sb.append('(');
build(n, open + 1, close, sb, res);
sb.deleteCharAt(sb.length() - 1);
}
if (close < open) { // only close what is open
sb.append(')');
build(n, open, close + 1, sb, res);
sb.deleteCharAt(sb.length() - 1);
}
}
}!Common mistake
Generating all 2^(2n) strings and filtering valid ones.
Complexity
- Time: O(4^n / √n) — the Catalan number of results.
- Space: O(n).
Topic: Recursion & Backtracking
🎬 Episodes 29–36: video coming soon