leetcode（python）22.括号生成

22.括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

题目链接：https://leetcode.com/problems/generate-parentheses/

该题与第20题有效的括号有些许相似之处，其中一种暴力解法是：有一个2*n长度的数组，每一个位置可以放’(’ 或者 ‘)’，然后找满足条件的解。

这里 ，用DP求解。
思路：因为只有一对（）号，那么其他的（）位于其中间或者外面，即（（））或者（）（）,在其基础上如此下去，便可得到最终解。

class Solution:
    def generateParenthesis(self, n):
          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]