24.Generate Parentheses
Problem
Given an integer n, return all combinations of n pairs of parentheses that are well-formed (every '(' is closed by a later ')', and no prefix closes more than it opens). The order of the output does not matter.
Examples
Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]Input: n = 1
Output: ["()"]Constraints
1 <= n <= 8
💡 Key Insight
A partial string can still become valid iff (1) it has used at most n opening brackets and (2) it never has more ')' than '('. So build the string one character at a time and only add '(' while open < n, and only add ')' while close < open. Every path of this search ends in a valid answer — no wasted work on dead branches.
Brute Force (Generate and Validate)
TimeO(2^(2n) · n)SpaceO(n)Intuition
Each position of a length-2n string is either '(' or ')', giving 2^(2n) strings. Generate them all and keep those that are balanced (running balance never negative and ends at zero).
Algorithm
- Recursively fill a
char[2n]with every combination of'('and')'. - When full, check validity with a running
balancecounter. - Add valid strings to the result.
Visualization
n = 1 → all length-2 strings:
"((" balance ends 2 ✗
"()" balance 1 → 0 ✓
")(" balance goes -1 ✗
"))" balance goes -1 ✗Code
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
generate(new char[2 * n], 0, result);
return result;
}
private void generate(char[] current, int pos, List<String> result) {
if (pos == current.length) {
if (isValid(current)) {
result.add(new String(current));
}
return;
}
current[pos] = '(';
generate(current, pos + 1, result);
current[pos] = ')';
generate(current, pos + 1, result);
}
private boolean isValid(char[] s) {
int balance = 0;
for (char c : s) {
balance += (c == '(') ? 1 : -1;
if (balance < 0) {
return false; // closed more than opened
}
}
return balance == 0;
}
}Complexity
- Time: O(2^(2n) · n) — every one of the
4^nstrings is built and validated in O(n). - Space: O(n) — recursion depth
2n(excluding the output).
Dynamic Programming (Closure Number)
TimeO(4^n / √n)SpaceO(4^n / √n)Intuition
Every valid string with k pairs can be written uniquely as "(" + A + ")" + B, where the first '(' is matched by the ')' after A. A is a valid string with i pairs and B with k - 1 - i pairs. So build the answers for 0, 1, ..., n pairs from smaller ones.
Algorithm
dp[0] = [""].- For
kfrom1ton, forifrom0tok - 1:- For every
aindp[i]andbindp[k - 1 - i], add"(" + a + ")" + btodp[k].
- For every
- Return
dp[n].
Dry Run
| k | Built from | dp[k] |
|---|---|---|
| 0 | — | "" |
| 1 | (dp0)dp0 |
() |
| 2 | (dp0)dp1, (dp1)dp0 |
()(), (()) |
| 3 | (dp0)dp2, (dp1)dp1, (dp2)dp0 |
()()(), ()(()), (())(), (()()), ((())) |
Code
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<String> generateParenthesis(int n) {
List<List<String>> dp = new ArrayList<>();
dp.add(List.of("")); // zero pairs: the empty string
for (int k = 1; k <= n; k++) {
List<String> current = new ArrayList<>();
for (int i = 0; i < k; i++) {
// i pairs inside the first bracket, k-1-i pairs after it
for (String inside : dp.get(i)) {
for (String after : dp.get(k - 1 - i)) {
current.add("(" + inside + ")" + after);
}
}
}
dp.add(current);
}
return dp.get(n);
}
}Complexity
- Time: O(4^n / √n) — level
kproduces the Catalan numberC(k) ~ 4^k / (k√k)strings, each costing O(k) to build; the last level dominates. - Space: O(4^n / √n) — every intermediate list is kept, dominated by
dp[n].
BacktrackingOptimal
TimeO(4^n / √n)SpaceO(n)Intuition
Only make choices that keep the prefix valid:
- add
'('ifopen < n; - add
')'ifclose < open.
When the length reaches 2n, the string is guaranteed valid. A single StringBuilder is reused — append, recurse, then remove the last character (backtrack).
Algorithm
backtrack(sb, open, close):- If
sb.length() == 2n, recordsb.toString()and return. - If
open < n: append'(', recurse withopen + 1, remove last char. - If
close < open: append')', recurse withclose + 1, remove last char.
- If
- Call
backtrack("", 0, 0).
Dry Run
flowchart TD
R["'' (0,0)"] --> A["'(' (1,0)"]
A --> B["'((' (2,0)"]
A --> C["'()' (1,1)"]
B --> D["'(((' → '((()))'"]
B --> E["'(()' (2,1)"]
E --> F["'(()(' → '(()())'"]
E --> G["'(())' → '(())()'"]
C --> H["'()(' (2,1)"]
H --> I["'()((' → '()(())'"]
H --> J["'()()' → '()()()'"]Each node shows the prefix and (open, close); branches are cut whenever a choice would break validity, so all 5 leaves are answers for n = 3.
Code
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
backtrack(new StringBuilder(), 0, 0, n, result);
return result;
}
private void backtrack(StringBuilder sb, int open, int close, int n, List<String> result) {
if (sb.length() == 2 * n) {
result.add(sb.toString()); // always valid by construction
return;
}
if (open < n) {
sb.append('(');
backtrack(sb, open + 1, close, n, result);
sb.deleteCharAt(sb.length() - 1); // undo choice
}
if (close < open) {
sb.append(')');
backtrack(sb, open, close + 1, n, result);
sb.deleteCharAt(sb.length() - 1);
}
}
}Complexity
- Time: O(4^n / √n) — there are
C(n) ~ 4^n / (n√n)valid strings, each costing O(n) to copy out, and no dead branches are explored. - Space: O(n) — recursion depth and the shared
StringBuilder(excluding the output).
Complexity Comparison
| Approach | Time | Space (excl. output) |
|---|---|---|
| Brute Force (generate + validate) | O(4^n · n) | O(n) |
| Dynamic Programming | O(4^n / √n) | O(4^n / √n) |
| Backtracking | O(4^n / √n) | O(n) |
Common Pitfalls
- Allowing
')'whenclose < ninstead ofclose < open— produces strings like")(". - Forgetting to remove the last character after recursing when sharing a
StringBuilder— later branches see stale characters. - Adding
sbitself (notsb.toString()) to the result list — every entry would point to the same mutating builder. - Assuming a specific output order; LeetCode accepts any order.