To generate all npair parentheses, we can do the following:

Generate one pair: ()

Generate 0 pair inside, n  1 afterward: () (...)...
Generate 1 pair inside, n  2 afterward: (()) (...)...
...
Generate n  1 pair inside, 0 afterward: ((...))
I bet you see the overlapping subproblems here. Here is the code:
(you could see in the code that x
represents one jpair solution and y
represents one (i  j  1) pair solution, and we are taking into account all possible of combinations of them)
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
dp = [[] for i in range(n + 1)]
dp[0].append('')
for i in range(n + 1):
for j in range(i):
dp[i] += ['(' + x + ')' + y for x in dp[j] for y in dp[i  j  1]]
return dp[n]