38. Generate Parentheses
mediumAsked at OlaGenerate 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. Brute force generate-and-filter
Generate every string of length 2n and keep the valid ones.
- Time
- O(2^(2n) * n)
- Space
- O(2^(2n))
// generate every binary string of length 2n and validate; omitted for brevityTradeoff:
2. Backtracking with counts
Track open and close used; only add '(' while open<n and ')' while close<open.
- Time
- O(catalan(n))
- Space
- O(n)
function generateParenthesis(n) {
const out = [];
const dfs = (s, open, close) => {
if (s.length === 2*n) { out.push(s); return; }
if (open < n) dfs(s+'(', open+1, close);
if (close < open) dfs(s+')', open, close+1);
};
dfs('', 0, 0);
return out;
}Tradeoff:
Ola-specific tips
Ola engineers like to see invariant-driven backtracking; tie it to enumerating valid pickup-dropoff sequences within a shared-ride.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.