Generate Parentheses
Problem
n pairs of parentheses, list every string of length
2n made of '(' and ')' that is balanced (every
prefix has at least as many opens as closes, and the totals match). Any order is fine.n = 3Output[((())),(()()),(())(),()(()),()()()]n = 1Output[()]1 ≤ n ≤ 8 · answer size = n-th Catalan number Cn (C8 = 1430)
Try it yourself
class Solution {
public List<String> generateParenthesis(int n) {
}
}
'(' while open < n, and ')' while
close < open. Following them means every leaf is valid — no
dead branches, no final check.Instinct Return ALL combinations, permutations, partitions or placements - or ask if any arrangement works - build a candidate step by step and undo each choice.
Memory hack Choose, explore, un-choose - walk the decision tree and snip a branch the moment it can no longer succeed.
Open the Backtracking guide →Approaches
Brute ForceGenerate All 22n Strings, Then Validate
O(22n · n)Space O(n)Recursively place either bracket at every one of the 2n positions,
then keep a finished string only if a running balance never goes negative and ends
at 0. Almost all of the 4n strings are rejected.
public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); generateAll(new char[2 * n], 0, res); return res; } private void generateAll(char[] cur, int pos, List<String> res) { if (pos == cur.length) { if (isValid(cur)) res.add(new String(cur)); return; } cur[pos] = '('; generateAll(cur, pos + 1, res); cur[pos] = ')'; generateAll(cur, pos + 1, res); } private boolean isValid(char[] cur) { int balance = 0; for (char c : cur) { balance += c == '(' ? 1 : -1; if (balance < 0) return false; } return balance == 0; }
Clearly correct, but explores 4n leaves to keep only Cn.
BetterClosure Number (Divide by First Pair)
O(4n/√n)Space O(4n/√n)Every valid string is uniquely "(" + A + ")" + B, where the first
'(' closes after A (c pairs) and B
has n-1-c pairs. Build lists for smaller sizes and combine them.
public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); if (n == 0) { res.add(""); return res; } for (int c = 0; c < n; c++) for (String inner : generateParenthesis(c)) for (String rest : generateParenthesis(n - 1 - c)) res.add("(" + inner + ")" + rest); return res; }
No invalid strings, but rebuilds sub-lists repeatedly and holds them all in memory.
OptimalBacktracking with Open/Close Counts
O(4n/√n)Space O(n)Grow one StringBuilder: try '(' if
open < n, try ')' if close < open, and
undo after each recursive call. Invalid prefixes are never created, so the work is
proportional to the Cn answers times their length.
public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); backtrack(res, new StringBuilder(), 0, 0, n); return res; } private void backtrack(List<String> res, StringBuilder cur, int open, int close, int n) { if (cur.length() == 2 * n) { res.add(cur.toString()); return; } if (open < n) { cur.append('('); backtrack(res, cur, open + 1, close, n); cur.deleteCharAt(cur.length() - 1); // undo } if (close < open) { cur.append(')'); backtrack(res, cur, open, close + 1, n); cur.deleteCharAt(cur.length() - 1); // undo } }
Output-sensitive, O(n) extra space — the canonical backtracking answer.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Generate All 22n Strings, Then Validate | O(22n · n) | O(n) |
| Better | Closure Number (Divide by First Pair) | O(4n/√n) | O(4n/√n) |
| Optimal | Backtracking with Open/Close Counts | O(4n/√n) | O(n) |
- Allowing
')'whenclose == open— creates invalid prefixes. - Checking only the final balance —
")("has balance 0 but is invalid. - Forgetting to undo the append (
deleteCharAt) after recursing.
- Mention the brute force, then show how the two counting rules prune it.
- Know the count: the answer size is the Catalan number Cn.
- Explain why a
StringBuilder+ undo beats creating a new string per call.