Generate Parentheses

Explanation & Solution

Description

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

A parentheses string is well-formed if every opening parenthesis ( has a corresponding closing parenthesis ) and the pairs are properly nested.

Input: n = 3

Output:["((()))","(()())","(())()","()(())","()()()"]

((()))

(()())

(())()

()(())

()()()

Explanation: All 5 valid arrangements of 3 pairs of parentheses.

Subsets pattern

Create an empty result array to collect all valid parentheses strings
Start the recursive backtrack function with an empty string and both open and close counts at 0

If the current string has length 2 * n, it contains exactly n opening and n closing parentheses
Add it to result and return

If the count of opening parentheses open is less than n, we can still add a (
Recurse with the updated string and open + 1

If the count of closing parentheses close is less than open, we can add a )
This condition ensures we never have more closing than opening parentheses at any point, maintaining validity
Recurse with the updated string and close + 1

By always trying ( before ), the results naturally come out in lexicographic order (since ( has a smaller ASCII value than ))
The two constraints (open < n and close < open) are necessary and sufficient to guarantee every generated string is well-formed

The key constraint is close < open: we can only add a closing parenthesis when there is an unmatched opening parenthesis to close
This simple rule eliminates all invalid strings without needing any explicit validation
The number of valid strings is the nth Catalan number: C(n) = (2n)! / ((n+1)! * n!)

Time

**O(4^n / sqrt(n))** — proportional to the nth Catalan number

Space

O(n) for the recursion depth

Input:

Backtracking Exploration

current path

empty

No animation available

ExploringFoundBacktrack

0 steps