Skip to main content

38. Generate Parentheses

mediumAsked at Reddit

Generate all combinations of n pairs of well-formed parentheses. Reddit uses this backtracking problem to test pruning skills — the same shape they'd use to enumerate valid markdown nesting structures during comment rendering.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit on-site question for backend roles.

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) strings and filter

Enumerate every string of length 2n made of ( and ). Keep valid ones.

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

Tradeoff: Generates 2^16 strings for n=8 then filters. Wasteful.

2. Backtracking with open/close counters (optimal)

At each step, add '(' if open < n, add ')' if close < open. Add to result when length = 2n.

Time
O(C(n) * n) where C is Catalan
Space
O(n) recursion
function generateParenthesis(n) {
  const out = [];
  function backtrack(current, open, close) {
    if (current.length === 2 * n) {
      out.push(current);
      return;
    }
    if (open < n) backtrack(current + '(', open + 1, close);
    if (close < open) backtrack(current + ')', open, close + 1);
  }
  backtrack('', 0, 0);
  return out;
}

Tradeoff: Only valid prefixes are extended. Output count is the nth Catalan number.

Reddit-specific tips

Reddit interviewers want the pruning insight — never generate invalid prefixes. Bonus signal: mention the result count is Catalan(n) (1, 1, 2, 5, 14, 42, ...) and connect to balanced markdown structures.

Common mistakes

  • Allowing close > open at any point (generates invalid strings).
  • Adding to result only when both counts hit n separately (must check length).
  • Mutating a string buffer without restoring state (in mutable-string languages).

Follow-up questions

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

  • Valid parentheses (LC 20) — the validation half.
  • Different ways to add parentheses (LC 241).
  • Longest valid parentheses (LC 32).

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(n)?

Balanced parens are equivalent to Dyck paths. Catalan numbers count Dyck paths of length 2n.

Could memoization help?

Every valid string is unique. No subproblem overlap to exploit.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →