LeetCode-22. 括号生成【字符串 动态规划 回溯】

题目描述：

解题思路一：动态规划

推导公式是：
“(” + 【i=p时所有括号的排列组合】 + “)” + 【i=q时所有括号的排列组合】

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return []
        total_l = []
        total_l.append([None])    # 0组括号时记为None
        total_l.append(["()"])    # 1组括号只有一种情况
        for i in range(2,n+1):    # 开始计算i组括号时的括号组合
            l = []        
            for j in range(i):    # 开始遍历 p q ，其中p+q=i-1 , j 作为索引
                now_list1 = total_l[j]    # p = j 时的括号组合情况
                now_list2 = total_l[i-1-j]    # q = (i-1) - j 时的括号组合情况
                for k1 in now_list1:  
                    for k2 in now_list2:
                        if k1 == None:   k1 = ""
                        if k2 == None:   k2 = ""
                        el = "(" + k1 + ")" + k2
                        l.append(el)    # 把所有可能的情况添加到 l 中
            total_l.append(l)    # l这个list就是i组括号的所有情况，添加到total_l中，继续求解i=i+1的情况
        return total_l[n]

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

解题思路二：回溯，回溯三部曲

1. 递归函数参数
   这里的参数是：
   :param cur_str: 从根结点到叶子结点的路径字符串
   :param left: 左括号还可以使用的个数
   :param right: 右括号还可以使用的个数

2. 递归终止条件
   在左边和右边剩余的括号数都等于 0 的时候结算。

3. 单层搜索的逻辑
   当前左右括号都有大于 0 个可以使用的时候，才产生分支；
   产生左分支的时候，只看当前是否还有左括号可以使用；
   产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以产生分支；

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        self.backtracking("", n, n, res)
        return res
    
    def backtracking(self, s, left, right, res):
        if left == 0 and right == 0:
            res.append(s)
        if right < left:
            return
        if left > 0:
            self.backtracking(s + '(', left - 1, right, res)
        if right > 0:
            self.backtracking(s + ')', left, right - 1, res)

时间复杂度：O(n⋅C(2n,n))
空间复杂度：O(n)
如果我们不用减法，使用加法，即 left 表示「左括号使用了几个」，right 表示「右括号使用了几个」，可以画出另一棵递归树。

from typing import List


class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        res = []
        cur_str = ''

        def dfs(cur_str, left, right, n):
            """
            :param cur_str: 从根结点到叶子结点的路径字符串
            :param left: 左括号已经使用的个数
            :param right: 右括号已经使用的个数
            :return:
            """
            if left == n and right == n:
                res.append(cur_str)
                return
            if left < right:
                return

            if left < n:
                dfs(cur_str + '(', left + 1, right, n)

            if right < n:
                dfs(cur_str + ')', left, right + 1, n)

        dfs(cur_str, 0, 0, n)
        return res

解题思路三：0

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