```
class Solution(object):
def __init__(self):
self.ans = {0: [''], 1: ['()']}
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
if n in self.ans:
return self.ans[n]
seqs = []
for i in xrange(n):
seqs += [a + '(' + b + ')' for a in self.generateParenthesis(i) for b in self.generateParenthesis(n - 1 - i)]
self.ans[n] = seqs
return seqs
```