Skip to main content

38. Generate Parentheses

mediumAsked at Snowflake

Generate all valid parenthesizations of n pairs. Snowflake uses this to test pruning during backtracking — the same instinct a query planner uses to cut off candidate-plan generation when constraints prove a partial plan can't extend to a valid full plan.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this to set up plan-enumeration follow-up.
  • LeetCode Discuss (2025-10)— Reported at Snowflake new-grad onsites.

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

Try every binary string of length 2n; keep the ones that are balanced.

Time
O(2^(2n) * n)
Space
O(2^(2n))
function generateParenthesis(n) {
  const result = [];
  function isValid(s) {
    let count = 0;
    for (const c of s) {
      if (c === '(') count++;
      else count--;
      if (count < 0) return false;
    }
    return count === 0;
  }
  function gen(s) {
    if (s.length === 2 * n) {
      if (isValid(s)) result.push(s);
      return;
    }
    gen(s + '(');
    gen(s + ')');
  }
  gen('');
  return result;
}

Tradeoff: Exponential, generates 2^(2n) candidates, validates each. Wasteful.

2. Backtracking with prune (optimal)

Track count of open and close used so far. Add '(' only if open < n; add ')' only if close < open. Prune invalid prefixes.

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

Tradeoff: Generates only valid strings. The 'close < open' constraint prunes invalid branches at the root.

Snowflake-specific tips

Snowflake interviewers want the prune conditions stated cleanly: 'open < n' and 'close < open'. Bonus signal: connect to plan enumeration — when the planner builds physical plans bottom-up, it prunes a subplan the moment a constraint (e.g., interesting orderings) proves it can't extend to a winning plan.

Common mistakes

  • Pruning only at the end (filter approach) — misses the point of backtracking.
  • Using close > open instead of close < open as the gate for adding ')'.
  • Returning all strings even when one branch couldn't extend (treating filtered as final result).

Follow-up questions

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

  • Catalan number meaning — how many valid strings are there?
  • Variations: parentheses of multiple types.
  • How does the planner prune during plan enumeration?

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 are close < open and open < n the right prunes?

close < open ensures we never close more than we've opened. open < n caps total opens. Together they generate exactly the Catalan number of strings.

Why is this called backtracking and not DFS?

Same shape; 'backtracking' emphasizes pruning invalid partial solutions. DFS plus prune == backtracking in CS terminology.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →