loading

22. Generate Parentheses — Step-by-Step Visualization

mediumLeetCode #22BacktrackingString

Given `n` pairs of parentheses, write a function to generate all combinations of well-formed parentheses. **Example 1:** Input: `n = 3` Output: `["((()))","(()())","(())()","()(())","()()()"]` **Example 2:** Input: `n = 1` Output: `["()"]` **Constraints:** - `1 <= n <= 8`

Algorithm Pattern

Backtracking Branch Constraints

Key Idea

We sequentially build a string of brackets but only branch if it doesn't violate rules: open_count < n and closed_count < open_count.

Step-by-Step Approach

  1. Track `openN` (count of `(`) and `closedN` (count of `)`).
  2. If we haven't placed `n` opening brackets yet (`openN < n`), we can branch by adding `(`.
  3. If we have more open brackets than closed ones (`closedN < openN`), we can branch by adding `)`.
  4. When both `openN` and `closedN` reach `n`, we've formed a completely valid string combination of length `2 * n`.

Common Gotchas

  • Attempting to generate *all* combinations of `2 * n` characters and then validating them is incredibly slow.
  • Appending backwards via immutable tracking strings eliminates popping requirements within the recursion context, drastically reducing state-leak errors.

Related Problems

← All problems