```
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
self.n = n
self.res = []
self.dfs(0, 0, [])
return self.res
def dfs(self, i, j, path):
if i == self.n:
while len(path) != self.n * 2:
path.append(")")
self.res.append("".join(path))
return
self.dfs(i+1, j, path+["("])
if j < i:
self.dfs(i, j+1, path+[")"])
return
```

i is the count of "(" and j is the count of ")".

The first character always has to be a opening parenthesis and then the next can either be another opening parenthesis or closing parenthesis depending on the following rules:

- We cannot add a closing parenthesis if there are already the same amount of closing and opening parentheses
- We can only add closing parentheses if i is equal to n