20. Generate Parentheses
mediumAsked at GojekGenerate all combinations of n pairs of well-formed parentheses.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Constraints
1 <= n <= 8
Examples
Example 1
Input
n = 3Output
["((()))","(()())","(())()","()(())","()()()"]Example 2
Input
n = 1Output
["()"]Approaches
1. Generate then filter
Generate all 2^(2n) binary strings, keep only the balanced ones.
- Time
- O(2^(2n) * n)
- Space
- O(2^(2n))
const out = [];
const gen = p => {
if (p.length === 2*n) { if (valid(p)) out.push(p); return; }
gen(p + '('); gen(p + ')');
};Tradeoff:
2. Backtrack with counts
Track open and close counts; only add '(' while open < n and only add ')' while close < open. Every leaf is automatically balanced.
- Time
- O(C_n)
- Space
- O(n)
function generateParenthesis(n) {
const out = [];
const dfs = (cur, open, close) => {
if (cur.length === 2 * n) { out.push(cur); return; }
if (open < n) dfs(cur + '(', open + 1, close);
if (close < open) dfs(cur + ')', open, close + 1);
};
dfs('', 0, 0);
return out;
}Tradeoff:
Gojek-specific tips
Gojek expects candidates to prune early in recursion, the same instinct that prevents fanout explosions across regionally partitioned dispatch microservices.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.