## Generate parentheses

Given `n`

, write a function to generate all combinations of well-formed parentheses. This problem can be solved in LeetCode.

## Examples

```
n = 1
["()"]
n = 2
["(())", "()()"]
n = 3
["((()))", "(()())", "(())()", "()(())", "()()()"]
```

## Solution

If the problem is to find the number of the combination, this is a Catalan number sequence problem. However, we need to print all combinations. Therefore, this is a typical backtracking search problem because we need to explore every possible outcomes.

Let's look at the code first.

```
from typing import List
def generate_parenthesis(n: int) -> List[str]:
"""Generate all combinations of well-formed parentheses
Example:
>>> generate_parenthesis(3)
['((()))', '(()())', '(())()', '()(())', '()()()']
"""
def backtrack(current: str,
left: int,
right: int,
result: List[str] = []) -> List[str]:
if len(current) == 2 * n:
result.append(current)
if left < n:
backtrack(current + "(", left + 1, right)
if right < left:
backtrack(current + ")", left, right + 1)
return result
return backtrack("", 0, 0)
```

One way of tackling this problem is to track the number of open(left) parentheses and the number of close(right) parentheses.

Suppose

the number of open parentheses`left`

:the number of close parentheses`right`

:

Then,

- We know we can have
`n`

open parentheses and`n`

close parentheses - Therefore, add a open parenthesis as long as
`left < n`

. - We can only add a closing parenthesis when
`right < left`

.

Notice that we don't break the validity of the parentheses as long as we close parentheses when `right < left`

.