Approach Summary
Backtracking: add "(" if open < n; add ")" if close < open. Collect when len = 2n.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Full Solution & Approach
Every valid sequence of n pairs must be a balanced parenthesis string: at every prefix the number of closing brackets never exceeds the number of opening brackets, and the total counts are exactly n each. Generate candidates recursively with a backtracking function that tracks how many opening and closing brackets are already placed. At each step you may place an opening bracket as long as open < n, and you may place a closing bracket as long as close < open — this second condition is what guarantees every prefix stays balanced. When the path reaches length 2n, record it as a complete sequence. The search tree is exactly the set of valid sequences with no wasted branches, so the total work is proportional to the number of valid sequences, which is the n-th Catalan number, roughly 4^n / (n^(3/2) √π). Backtracking by removing the last character after each recursive call keeps the path reusable without copying. This is the standard template for generating constrained combinatorial strings — the same skeleton solves phone-number letter combinations and restore-IP-addresses.
The algorithm explores exactly the valid sequences, whose count is the n-th Catalan number C(n) = (1/(n+1))·C(2n, n) — O(C(n)) time. Each valid sequence is built and stored once; the recursion depth is at most 2n, giving O(n) space for the path plus the output.
Solution Code
Solution
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
backtrack(n, 0, 0, new StringBuilder(), res);
return res;
}
private void backtrack(int n, int open, int close, StringBuilder path, List<String> res) {
if (path.length() == 2 * n) {
res.add(path.toString());
return;
}
if (open < n) {
path.append('(');
backtrack(n, open + 1, close, path, res);
path.deleteCharAt(path.length() - 1);
}
if (close < open) {
path.append(')');
backtrack(n, open, close + 1, path, res);
path.deleteCharAt(path.length() - 1);
}
}vector<string> generateParenthesis(int n) {
vector<string> res;
string path;
backtrack(n, 0, 0, path, res);
return res;
}
void backtrack(int n, int open, int close, string& path, vector<string>& res) {
if ((int)path.size() == 2 * n) {
res.push_back(path);
return;
}
if (open < n) {
path.push_back('(');
backtrack(n, open + 1, close, path, res);
path.pop_back();
}
if (close < open) {
path.push_back(')');
backtrack(n, open, close + 1, path, res);
path.pop_back();
}
}def generate_parenthesis(n: int) -> list[str]:
res = []
def backtrack(open_count: int, close_count: int, path: list[str]) -> None:
if len(path) == 2 * n:
res.append(''.join(path))
return
if open_count < n:
path.append('(')
backtrack(open_count + 1, close_count, path)
path.pop()
if close_count < open_count:
path.append(')')
backtrack(open_count, close_count + 1, path)
path.pop()
backtrack(0, 0, [])
return resfunction generateParenthesis(n) {
const res = [];
function backtrack(open, close, path) {
if (path.length === 2 * n) {
res.push(path.join(''));
return;
}
if (open < n) {
path.push('(');
backtrack(open + 1, close, path);
path.pop();
}
if (close < open) {
path.push(')');
backtrack(open, close + 1, path);
path.pop();
}
}
backtrack(0, 0, []);
return res;
}Edge Cases to Watch
- n = 0 — the problem returns [""] (one empty string)
- n = 1 — exactly ["()"]
- Unbalanced prefixes are never generated because close < open gates the closing branch
- n = 3 — the five classic sequences: ((())), (()()), (())(), ()(()), ()()()
Master the Backtracking Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Backtracking pattern.
How to Recognize This Pattern
- "All valid combinations of n pairs of parentheses"
- Constraint: close ≤ open ≤ n at all times
Complexity Analysis
Time Complexity
O(4ⁿ / √n)
Space Complexity
O(n)