Generate Parentheses

Longest Common Subsequence

House Robber III

Generate every well-formed parentheses string using exactly n pairs in canonical backtracking order.

Given an integer `n`, return every well-formed parentheses string that uses exactly `n` pairs of parentheses.

Return the answers in the deterministic order produced by backtracking that always tries appending `(` before `)` whenever both choices are allowed.

**Input / output**
- Input: `n: int`
- Output: `string[]` containing every valid combination in canonical backtracking order

**Examples**
1. `n = 3` returns `["((()))","(()())","(())()","()(())","()()()"]`.
2. `n = 1` returns `["()"]`.
3. `n = 0` returns `[""]` because there is exactly one valid sequence of zero pairs: the empty string.

**Constraints**
- `0 <= n <= 7`

**Target complexity**
- The optimal approach should build only valid prefixes, not all `2^(2n)` raw strings.

**Follow-up**
How would you count the number of valid combinations without generating them all, or generate them iteratively instead of recursively?

- Every answer is a length-`2n` string built one character at a time.
- A prefix is only worth continuing if it can still become valid: you can never close more parentheses than you have opened, and you can never open more than `n`.
- The required output order comes naturally if every recursive call tries `(` before `)`.

Understand the search tree

- A direct baseline is to generate every length-`2n` string of `(` and `)`, then keep only the balanced ones.
- This is correct and still respects the required order if you branch to `(` before `)`, but it wastes time exploring obviously impossible prefixes.

Start from a brute-force baseline

- Instead of generating bad strings and rejecting them later, track how many opens and closes you have used so far.
- You may add `(` only while `open_count < n`, and you may add `)` only while `close_count < open_count`.
- Those two rules guarantee every recursive prefix can still lead to a valid answer.

Prune invalid prefixes early

- This DFS builds only valid prefixes and automatically emits answers in the required canonical order because every call tries `(` before `)`.
- Once the current string reaches length `2n`, it is a complete answer.

Optimal backtracking solution

Trace `n = 3` with the optimal recursion.

1. Start with `""`, so the only legal move is `(`.
2. Repeatedly preferring `(` first reaches `"((()"`, then `"((())"`, then `"((()))"`, which becomes the first answer.
3. Backtrack one step at a time to the nearest prefix that still allows a different valid choice, producing `"(()())"`, then `"(())()"`, then `"()(())"`, then `"()()()"`.

Because every branch tries `(` before `)`, the results appear as `["((()))","(()())","(())()","()(())","()()()"]`.

Dry run

- Appending `)` when `close_count == open_count`, which creates an invalid prefix immediately.
- Forgetting to undo the last append before exploring the sibling branch.
- Returning a set or sorting afterward can hide bugs in the required canonical order.
- Follow-up: count combinations with Catalan DP when you need only the number, not the actual strings.

Common mistakes and follow-ups

- `n = 0` should return `[""]`, not `[]`, because there is one valid empty construction.
- `n = 1` returns exactly `["()"]`.
- Larger `n` values explode in output size, so the algorithm should avoid generating invalid branches at all.

Edge cases to test mentally

Backtracking with `( opens first, ) second` explores only valid prefixes, so it emits every well-formed string exactly once in canonical order. The runtime is `O(C_n * n)` and the output dominates space at `O(C_n * n)`, where `C_n` is the nth Catalan number; recursion itself uses `O(n)` extra stack space.