【递归 &回溯】Leecode-22. 括号生成

【题目】

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

【题解】

题解1：

• 思路

     dp

• 复杂度

         时间复杂度：O(n)，空间复杂度：O(n)

• 代码

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        dp = [[None], ["()"]]       # n=0,1
        for i in range(2,n+1):
            l = []
            for j in range(i):
                list_p = dp[j]
                list_q = dp[i-j-1]
                for p in list_p:
                    for q in list_q:
                        p = p if p else ""
                        q = q if q else ""
                        l.append('('+p+')'+q)
            dp.append(l)
        return dp[n]