Skip to main content

38. Generate Parentheses

mediumAsked at Ola

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. 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 brevity

Tradeoff:

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.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →