Skip to main content

22. Generate Parentheses

medium

Generate all combinations of n pairs of well-formed parentheses. The cleanest backtracking-with-constraints problem — and a great way to demo pruning intuition under time pressure.

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

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
["()"]

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute force all 2^(2n) strings and filter by validity. Works but wasteful.

Hint 2

Backtrack with two counters: openUsed and closeUsed. Two rules: can place '(' if openUsed < n; can place ')' if closeUsed < openUsed.

Hint 3

Recurse until length == 2n; add the string to the result.

Hint 4

The 'closeUsed < openUsed' rule is the pruning gold — never let close get ahead, and you'll never generate an invalid prefix.

Solution approach

Reveal approach

Backtracking. Recursive helper(current, openUsed, closeUsed): if len(current) == 2n, append current to result and return. If openUsed < n, recurse with current + '(' and openUsed + 1. If closeUsed < openUsed, recurse with current + ')' and closeUsed + 1. Start with helper('', 0, 0). The two if-rules act as live pruning — you never explore an invalid prefix. The recursion tree has exactly Catalan(n) = C(2n, n) / (n + 1) leaves and a branching factor of at most 2, giving O(4^n / sqrt(n)) total work — but in practice it's fast for the constraint n <= 8.

Complexity

Time
O(4^n / sqrt(n))
Space
O(4^n / sqrt(n)) for output, O(n) recursion stack

Related patterns

  • backtracking
  • stack
  • recursion

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Google
  • Microsoft
  • Uber

Practice these live with InterviewChamp.AI

Drill Generate Parentheses and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →