This solution uses a lot of extra space for memoization, but it's really easy to understand, compared to solutions which operate with individual '(' and ')'.

Idea: to get answer for N, get answers for 1..N-1 and combine them in various ways.

Sets make sure that we're not duplicating solutions.

```
class Solution(object):
def recur(self, n):
if self.res.has_key(n):
return self.res[n]
res_prev = self.recur(n-1)
res = set()
for x in res_prev:
res.add("(" + x + ")")
for lvl in xrange(1, n):
res_prev1 = self.recur(lvl)
res_prev2 = self.recur(n-lvl)
for x in res_prev1:
for y in res_prev2:
res.add(x + y)
res.add(y + x)
self.res[n] = res
return res
def generateParenthesis(self, n):
self.res = {0: set(), 1: set(["()"])}
return list(self.recur(n))
```