Skip to main content

38. Generate Parentheses

mediumAsked at Workday

Generate all valid parenthesis strings of n pairs. Workday uses this for backtracking + pruning — same shape as enumerating valid approval-chain templates.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 phone screen.

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

Enumerate every binary string of length 2n; keep valid ones.

Time
O(2^(2n) * n)
Space
O(2^(2n))
// brute generate, then validate each

Tradeoff: Massive wasted work; most strings are invalid.

2. Backtracking with open/close counters

At each step, append '(' if open < n, append ')' if close < open.

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

Tradeoff: Only generates valid strings — the two counters are the pruning invariant.

Workday-specific tips

Workday wants the pruning conditions stated explicitly: 'open' bounded above by n; 'close' bounded above by 'open'. Walk through both before coding. Mention the Catalan-number count if asked about complexity.

Common mistakes

  • Allowing close to exceed open — generates invalid strings.
  • Allowing open to exceed n — generates oversized strings.
  • Forgetting the base case length === 2 * n.

Follow-up questions

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

  • Different Ways to Add Parentheses (LC 241).
  • Valid Parentheses (LC 20).
  • What if we have multiple 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 close < open?

A valid string never has more closes than opens at any prefix. The condition encodes this invariant.

Catalan numbers?

The count of valid strings is C(n) = (2n)! / (n!(n+1)!). Grows as ~4^n / n^(3/2).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →