Skip to main content

38. Generate Parentheses

mediumAsked at Vercel

Generate all combinations of n pairs of well-formed parentheses. Vercel asks this for the constrained-backtracking pattern — same shape as enumerating valid nested route configurations under their layout-tree rules.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; constraint-pruned backtracking expected.
  • Blind (2026-Q1)— Mentioned in Vercel onsite recap.

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 all 2^(2n), filter by validity

Enumerate every binary string of length 2n; keep only the balanced ones.

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

Tradeoff: Exponential explosion. Mention only to motivate the pruned backtracking.

2. Backtracking with open/close counters (optimal)

Track open and close used so far. Can add '(' if open < n. Can add ')' if close < open. When both equal n, emit.

Time
O(4^n / sqrt(n)) Catalan
Space
O(n) recursion
function generateParenthesis(n) {
  const out = [];
  function 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: Catalan-number bounded — much smaller than 2^(2n). The two constraints (open <= n, close <= open) prune invalid prefixes early.

Vercel-specific tips

Vercel grades the constraint-pruned backtracking. Bonus signal: noting that the answer count is the n-th Catalan number (~4^n / (n*sqrt(n))) and that the two simple constraints (open < n, close < open) are sufficient — no need for a post-validity check.

Common mistakes

  • Adding `)` when close >= open — produces unbalanced prefixes.
  • Forgetting to recurse into '(' OR ')' — must consider both branches.
  • Building all 2^(2n) and filtering — passes but TLEs near n=8.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Longest valid parentheses (LC 32, hard).
  • Number of valid combinations — the n-th Catalan number.
  • K-balanced strings — different bracket types.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the count Catalan?

Valid parenthesis strings of length 2n are in bijection with Dyck paths, which are counted by Catalan numbers. C_n = (2n choose n) / (n+1).

Could I emit invalid prefixes and prune later?

You could, but the pruning at build time is strictly faster — every pruned branch was an invalid subtree you avoided exploring.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →