# LeetCode 22. Generate Parentheses

## Description

https://leetcode.com/problems/generate-parentheses/

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`

Accepted

## Explanation

We can use the backtracking algorithm to solve this problem. Given n number of left parentheses and right parentheses, try generate all possible combinations. If the combination turns to be not valid, the backtracking algorithm discards it and then try another combination.

## Python Solution

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

self.helper(n, n, "", result)

return result

def helper(self, left, right, out, result):
if left < 0 or right < 0 or left > right:
return

if left == 0 and right == 0:
result.append(out)
return

self.helper(left - 1, right, out + "(", result);
self.helper(left, right - 1, out + ")", result);
``````
• Time complexity: O(4^N/ N^1/2).
• Space complexity: O(4^N/ N^1/2).