Skip to main content

17. Generate Parentheses

mediumAsked at Ramp

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

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. Return the answer as a list of strings.

Constraints

  • 1 <= n <= 8

Examples

Example 1

Input
n = 3
Output
["((()))","(()())","(())()","()(())","()()()"]

Example 2

Input
n = 1
Output
["()"]

Approaches

1. Brute force generate-and-validate

Generate all 2^(2n) strings of length 2n, keep balanced ones.

Time
O(2^(2n) * n)
Space
O(2^(2n) * n)
function generateParenthesis(n) {
  const out = [];
  function valid(s) { let c = 0; for (const ch of s) { c += ch === '(' ? 1 : -1; if (c < 0) return false; } return c === 0; }
  function build(s) { if (s.length === 2 * n) { if (valid(s)) out.push(s); return; } build(s + '('); build(s + ')'); }
  build('');
  return out;
}

Tradeoff:

2. Backtracking with open/close counts

Track remaining opens and closes; only emit '(' if opens left and only emit ')' if closes outnumber opens already placed.

Time
O(4^n / sqrt(n))
Space
O(n)
function generateParenthesis(n) {
  const out = [];
  function build(cur, open, close) {
    if (cur.length === 2 * n) { out.push(cur); return; }
    if (open < n) build(cur + '(', open + 1, close);
    if (close < open) build(cur + ')', open, close + 1);
  }
  build('', 0, 0);
  return out;
}

Tradeoff:

Ramp-specific tips

Ramp uses this exact constraint-pruning style inside their approval-graph engine to enumerate valid policy paths without generating dead branches.

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 Ramp interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →