Generate Parentheses
Module 16 · Recursion & Backtracking
Problem
Given n pairs of parentheses, return all combinations of
well-formed (balanced, correctly nested) parenthesis strings of length
2n. (LeetCode 22.)
Examples
Example 1
n = 3Output["((()))","(()())","(())()","()(())","()()()"]Example 2
n = 1Output["()"]Constraints
1 ≤ n ≤ 8.
Attempt it first
This is a backtracking problem where the state-space tree's branching
looks simple — at each position, add ( or add ) — but most of that
naive tree is invalid strings. The concept lesson made a specific point
about this: pruning invalid branches during construction beats
generating everything and filtering afterward. Before opening anything,
work out: given how many ( and ) you've placed so far, what is the
exact rule for when it's still legal to place a (, and when it's still
legal to place a )? Get that rule right and the recursion is a direct
translation of it.