Skip to main content

20. Generate Parentheses

mediumAsked at Gojek

Generate all combinations of n pairs of well-formed parentheses.

By Alex Chen, 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 = 3
Output
["((()))","(()())","(())()","()(())","()()()"]

Example 2

Input
n = 1
Output
["()"]

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.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Generate Parentheses and other Gojek interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →