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]
网友评论