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 Sam K., 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

More Stacks practice problems

See all Stacks problems →