Skip to main content

22. Generate Parentheses

mediumAsked at Netflix

Given n pairs of parentheses, generate all combinations of well-formed parentheses. Netflix asks this to test whether you can prune a backtracking search with two simple invariants (open-count and close-count) instead of generating-then-filtering.

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

Source citations

Public interview reports confirming this problem appears in Netflix loops.

  • Glassdoor (2026-Q1)— Netflix SWE loop reports list this as the recursion-and-pruning question on the algorithms screen.
  • Reddit r/cscareerquestions (2025-11)— Reported in multiple Netflix new-grad / mid-level write-ups as a 30-minute backtracking warm-up.

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-then-validate

Generate every binary string of length 2n over '(' and ')', then validate each with a counter.

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

Tradeoff: Correct but exponential in the worst case at the upper constraint (2^16 = 65536 strings * O(n) validation). Mention it to motivate the prune.

2. Backtracking with open/close counters (optimal)

Track how many '(' and ')' you've placed. Recurse only when adding '(' if open < n, and only adding ')' if close < open. Each leaf is automatically valid.

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

Tradeoff: O(4^n / sqrt(n)) — the nth Catalan number — and O(n) stack. The two pruning conditions guarantee well-formed strings without any validation pass.

Netflix-specific tips

Netflix interviewers want the two prune invariants named explicitly before you write the recursion: 'I can only add a ( if I haven't placed all n yet, and I can only add a ) if there's an unmatched ( before it.' If you write the brute-force first and then prune, that's fine — narrate the transition. If you jump straight to the optimal, articulate the invariants anyway.

Common mistakes

  • Generating all 2^(2n) strings and filtering — passes but loses the pruning signal.
  • Tracking 'balance' instead of separate open/close counts — works but is harder to communicate.
  • Forgetting the base case s.length === 2 * n and stopping at n instead.

Follow-up questions

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

  • Valid Parentheses (LC 20) — the validation variant.
  • Remove Invalid Parentheses (LC 301) — given a string with invalid parens, return all valid removal results.
  • Count parentheses without generating — Catalan number formula (n+1 C 2n) / (n+1).

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 answer count the nth Catalan number?

Every valid sequence of n pairs corresponds to a Dyck path of length 2n staying non-negative. The Catalan numbers count these. Concretely C(n) = (2n choose n) / (n + 1), which grows like 4^n / (n^(3/2) sqrt(pi)).

Could I solve this with DP instead of backtracking?

Yes — solutions(n) = union over i in [0..n-1] of '(' + solutions(i) + ')' + solutions(n-1-i). It's a nice closure-based variant, same asymptotic count.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →