# LeetCode 22: Generate Parentheses

## Problem Restatement

We are given an integer `n`.

We need to generate all combinations of well-formed parentheses using exactly `n` pairs.

For example, if:

```text
n = 3
```

then every result must contain:

```text
3 opening parentheses
3 closing parentheses
```

and the parentheses must be valid.

The problem asks for all valid strings, not just the number of valid strings. The constraint is `1 <= n <= 8`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer `n` |
| Output | All well-formed parentheses strings using `n` pairs |
| Opening count | Exactly `n` |
| Closing count | Exactly `n` |
| Constraint | `1 <= n <= 8` |

Example function shape:

```python
def generateParenthesis(n: int) -> list[str]:
    ...
```

## Examples

Example 1:

```text
n = 3
```

Output:

```text
["((()))", "(()())", "(())()", "()(())", "()()()"]
```

Example 2:

```text
n = 1
```

Output:

```text
["()"]
```

## First Thought: Generate Every String

One possible approach is to generate every string of length `2n` made of `(` and `)`.

For `n = 3`, every candidate has length `6`.

Each position has two choices:

```text
(
)
```

So there are:

```text
2^(2n)
```

candidate strings.

After generating each string, we check whether it is valid.

This works, but it wastes work because most strings are invalid.

For example:

```text
")))((("
```

can never become valid. We should avoid generating invalid prefixes.

## Key Insight

Build the string from left to right.

At any point, we only need two counts:

| Count | Meaning |
|---|---|
| `open_count` | Number of `(` already used |
| `close_count` | Number of `)` already used |

We can add `(` if:

```text
open_count < n
```

We can add `)` if:

```text
close_count < open_count
```

The second rule is important.

It prevents invalid prefixes like:

```text
")"
"())"
```

A closing parenthesis is only valid if there is an unmatched opening parenthesis before it.

## Backtracking Tree

For:

```text
n = 2
```

Start with an empty path.

We can add `(`:

```text
(
```

From there, we can add another `(`:

```text
((
```

Now we cannot add more `(` because `open_count == n`.

We must add `)`:

```text
(()
```

Then add the final `)`:

```text
(())
```

Backtrack and try another branch:

```text
()
```

Then add `(`:

```text
()(
```

Then add `)`:

```text
()()
```

So the answer for `n = 2` is:

```text
["(())", "()()"]
```

## Algorithm

1. Create an empty result list.
2. Create an empty path list.
3. Define a backtracking function with:
   - `open_count`
   - `close_count`
4. If the path length is `2 * n`, add the path as a string.
5. If `open_count < n`, add `(` and recurse.
6. If `close_count < open_count`, add `)` and recurse.
7. Return the result list.

## Correctness

The algorithm only adds `(` when fewer than `n` opening parentheses have been used. So no generated string can contain more than `n` opening parentheses.

The algorithm only adds `)` when `close_count < open_count`. So at every prefix, the number of closing parentheses never exceeds the number of opening parentheses.

These two rules are exactly the conditions needed for a parentheses string to remain valid while being built left to right.

When the path length reaches `2 * n`, the string has exactly `n` opening parentheses and exactly `n` closing parentheses. Since every prefix has stayed valid, the completed string is well-formed.

The algorithm tries every legal choice at every step, so every well-formed parentheses string is eventually generated.

Therefore the algorithm returns exactly all valid combinations.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(C_n * n)` | There are `C_n` valid strings, each of length `2n` |
| Space | `O(C_n * n)` | The result stores all valid strings |

`C_n` is the nth Catalan number, the number of valid parentheses strings with `n` pairs.

The recursion path uses `O(n)` extra space.

## Implementation

```python
class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        result = []
        path = []

        def backtrack(open_count: int, close_count: int) -> None:
            if len(path) == 2 * n:
                result.append("".join(path))
                return

            if open_count < n:
                path.append("(")
                backtrack(open_count + 1, close_count)
                path.pop()

            if close_count < open_count:
                path.append(")")
                backtrack(open_count, close_count + 1)
                path.pop()

        backtrack(0, 0)

        return result
```

## Code Explanation

The result list stores complete valid strings:

```python
result = []
```

The path stores the current partial string:

```python
path = []
```

The helper function receives the number of opening and closing parentheses already used:

```python
def backtrack(open_count: int, close_count: int) -> None:
```

When the path reaches length `2 * n`, it is complete:

```python
if len(path) == 2 * n:
    result.append("".join(path))
    return
```

Add an opening parenthesis only if we still have one available:

```python
if open_count < n:
    path.append("(")
    backtrack(open_count + 1, close_count)
    path.pop()
```

Add a closing parenthesis only if it can close a previous opening parenthesis:

```python
if close_count < open_count:
    path.append(")")
    backtrack(open_count, close_count + 1)
    path.pop()
```

Start from no parentheses used:

```python
backtrack(0, 0)
```

## Testing

```python
def normalize(values):
    return sorted(values)

def run_tests():
    s = Solution()

    assert normalize(s.generateParenthesis(1)) == ["()"]

    assert normalize(s.generateParenthesis(2)) == [
        "(())",
        "()()",
    ]

    assert normalize(s.generateParenthesis(3)) == [
        "((()))",
        "(()())",
        "(())()",
        "()(())",
        "()()()",
    ]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `n = 1` | Smallest input |
| `n = 2` | Shows both nesting and adjacency |
| `n = 3` | Standard example |