Skip to main content

38. Generate Parentheses

mediumAsked at Plaid

Generate all combinations of n well-formed parentheses. Plaid asks this as a backtracking pattern problem before harder nested-JSON validation work on webhook payloads.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • LeetCode Discuss (2026)— Plaid SWE II OA backtracking.
  • Glassdoor (2025)— Plaid intro to backtracking.

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, filter valid

Brute force all strings of '(' and ')'; validate each.

Time
O(2^(2n) * n)
Space
O(n)
// Generate then filter. Don't ship — too wasteful.

Tradeoff: Exponential with a large constant. Mention only as the warm-up.

2. Backtracking with open/close counts

Track open and close counts. Add '(' if open < n. Add ')' if close < open. The constraint prunes invalid branches early.

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

Tradeoff: Pruned exploration. The output count is the Catalan number C(n), which is roughly 4^n / n^(3/2).

Plaid-specific tips

Plaid grades this on whether the constraints (open < n) and (close < open) come naturally. Bonus signal: connect this to nested-JSON parsing — the same constraint structure governs whether a webhook payload is well-formed.

Common mistakes

  • Allowing close > open in the recursion — produces invalid strings.
  • Off-by-one in the base case (path.length === n vs 2 * n).
  • Using a single counter (balance) — works but mixing two concepts.

Follow-up questions

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

  • Different generation strategies — DP, closure-number.
  • Validate parentheses (LC 20).
  • Longest valid parentheses (LC 32) — harder.

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 two counters?

open counts remaining capacity to push '('; close enforces 'can only close what's open.' Splitting makes the invariants explicit.

What's the output size?

Catalan numbers: 1, 2, 5, 14, 42, 132 for n = 1..6. Grows roughly as 4^n / n^(3/2).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →