Skip to main content

38. Generate Parentheses

mediumAsked at Datadog

Generate all combinations of n well-formed parentheses. Datadog asks this for the backtracking constraint-pruning pattern — the same idea applied to enumerating valid log-parser states.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite backtracking question.
  • LeetCode Discuss (2025-08)— Datadog tagged.

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

Enumerate every length-2n bracket string; keep only the valid ones.

Time
O(2^(2n) * n)
Space
O(2^(2n) * n)
// Generate every binary string interpreting 0 as '(' and 1 as ')';
// filter by isValid (stack-based). Too slow for n=8 (2^16 * 16 ops).

Tradeoff: Exponentially wasteful — most strings are invalid. Datadog will fail this for not pruning.

2. Backtracking with open/close counters (optimal)

Track (open used, close used). Add '(' if open < n. Add ')' if close < open. Emit when length = 2n.

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

Tradeoff: Prunes invalid prefixes immediately. The number of well-formed strings is the nth Catalan number — output size is C(n).

Datadog-specific tips

Datadog grades on whether you spot the two pruning rules: 'open < n' and 'close < open.' Both are needed; either alone produces a buggy enumeration. Articulate both BEFORE coding.

Common mistakes

  • Pruning only one of (open <= n) or (close <= open) — produces invalid strings.
  • Tracking string length instead of open/close counts — works but is less natural.
  • Forgetting that close < open (strict) is the rule, not close <= open — otherwise '()' at the start would let us emit ')' too early.

Follow-up questions

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

  • Different Ways to Add Parentheses (LC 241) — different operator placement.
  • Remove Invalid Parentheses (LC 301) — BFS variant.
  • Catalan numbers — closed-form count of the output size.

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?

We can only close a paren that's been opened. If close == open, all opens have been closed; adding ')' would make a prefix invalid like '())'.

How many outputs for n?

The nth Catalan number: C(n) = (2n choose n) / (n+1). C(8) = 1430.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →