Skip to main content

38. Generate Parentheses

mediumAsked at Salesforce

Given n pairs of parentheses, generate all combinations of well-formed parentheses. Salesforce uses this as a constrained-backtracking problem.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses this to test backtracking with constraint pruning.
  • Blind (2025-09)— Asked after LC 17 to test backtracking depth.

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

Generate all 2^(2n) strings of length 2n with '(' and ')'; keep the valid ones.

Time
O(2^(2n) * n)
Space
O(2^(2n))
function generateParenthesis(n) {
  const result = [];
  function gen(s) {
    if (s.length === 2 * n) { if (valid(s)) result.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 result;
}

Tradeoff: Exponential in n. Salesforce wants the pruned version.

2. Backtracking with open/close constraints

Place '(' if open < n; place ')' if close < open. Recurse.

Time
O(C(n))
Space
O(n) stack
function generateParenthesis(n) {
  const result = [];
  function dfs(s, open, close) {
    if (s.length === 2 * n) { result.push(s); return; }
    if (open < n) dfs(s + '(', open + 1, close);
    if (close < open) dfs(s + ')', open, close + 1);
  }
  dfs('', 0, 0);
  return result;
}

Tradeoff: Prunes invalid branches early. The total number of valid combinations is the nth Catalan number, so the algorithm is asymptotically optimal.

Salesforce-specific tips

Salesforce specifically tests whether you prune via constraints DURING recursion, not after. The (open < n) and (close < open) checks are the entire interview signal. Bonus signal: mention that the count of valid combinations equals the nth Catalan number — knowing this shows depth.

Common mistakes

  • Generating all 2^(2n) strings and filtering — exponential and obvious failure.
  • Allowing close < open to be flipped — produces things like ')(' which are invalid.
  • Forgetting the termination condition s.length === 2 * n — infinite recursion.

Follow-up questions

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

  • Valid Parentheses (LC 20) — checking, not generating.
  • Longest Valid Parentheses (LC 32) — hard.
  • Different Ways to Add Parentheses (LC 241).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

What's the time complexity exactly?

The nth Catalan number, which is C(2n, n) / (n+1) ~ 4^n / (n^1.5). Roughly exponential but tight.

Why prune with (close < open)?

Placing ')' before an open '(' creates an unclosed close, which can never become valid. Pruning here cuts the search space dramatically.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →