> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/backtracking/22generate-parentheses.md).

# 22\_Generate Parentheses

\[Medium]\[String, Backtracking]

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

**Example**:

```
Input: n = 3

Output:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
```

## Solution:

**Idea**:

* Generate parentheses one by one. At each position, there are 3 possibilities: 
  1. Add "(": if there are "(" remains to be added.
  2. Add ")": If the number of ")" is less than the number of "(" in the prefix.
* Write recursion at each position for the two possibilities.

**Time Complexity**: $$O(\frac{(2n)!}{n! (n+1)!})$$ from EPI page 235. Don't know how to compute.

**Space Complexity**: only need space for the output

```python
def generateParenthesis(n):
    """
    :type n: int
    :rtype: List[str]
    """        
    def helper(left, right, prefix):
        # left is the number of "(" remains to be added
        # right is the number of ")" remains to be added
        # prefix is the parentheses already added

        if right == 0:
            output.append(prefix)
            return

        # case when we are able to insert "("
        if left > 0:
            helper(left-1, right, prefix + "(")

        # case when we are able to insert ")"
        if right > left:
            helper(left, right - 1, prefix + ")")


    output = []
    helper(n, n, "")
    return output
```