MediumNeetCode150StringDynamic ProgrammingBacktracking
Generate Parentheses
Generate all valid n-parentheses combinations.
Examples
Input
n = 3
Output
5 combinations
5 valid arrangements.
Constraints
- •
1 <= n <= 8
Approaches
Generate all, check valid.
CodeT: O(2^(2n) * n) | S: O(2^(2n)) output
Add '(' or ')' based on counts.
CodeT: O(4^n / sqrt(n)) | S: O(n) stack depth
def generateParenthesis(n):
r=[]
def bt(s,lo,hi):
if len(s)==2*n: r.append(s); return
if lo<n: bt(s+'(',lo+1,hi)
if hi<lo: bt(s+')',lo,hi+1)
bt('',0,0); return rBuild from smaller n.
CodeT: O(4^n / sqrt(n)) | S: O(n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(2^(2n) * n) | O(2^(2n)) output | Generate all, check valid. |
| Backtracking | O(4^n / sqrt(n)) | O(n) stack depth | Add '(' or ')' based on counts. |
| DP | O(4^n / sqrt(n)) | O(n) | Build from smaller n. |
Brute Force
T: O(2^(2n) * n)S: O(2^(2n)) output
Generate all, check valid.
Backtracking
T: O(4^n / sqrt(n))S: O(n) stack depth
Add '(' or ')' based on counts.
DP
T: O(4^n / sqrt(n))S: O(n)
Build from smaller n.
Common Mistakes
Not tracking open/close count
Generating invalid paren
Off-by-one in n