leetcode hot100 括号生成

22. 括号生成

已解答

中等

相关标签

相关企业

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

class Solution(object):

    def generateParenthesis(self, n):

        """

        :type n: int

        :rtype: List[str]

        """

        self.ret=[]

        def dfs(count_left,count_right,current):

            if count_left==n and count_right==n:

                self.ret.append( current)

                return

            if count_left<=n:

                current +="("

                dfs(count_left+1,count_right,current)

                current = current[:-1]

            if count_right<count_left:

                current +=")"

                dfs(count_left,count_right+1,current)

                current = current[:-1]

        dfs(0,0,"")

        return self.ret

        # if n==0:

        #     return []

        # if n==1:

        #     return ["()"]

        # ret = []

        # ret.append([""])

        # ret.append(["()"])

        # for i in range(2,n+1):

        #     ret_t=[]

        #     for j in range(i):

        #         # print(ret)

        #         x = ret[j]

        #         y = ret[i-j-1]

        #         # ret_t=[]

        #         for k1 in x:

        #             for k2 in y:

        #                 ret_t.append("("+k1+")"+k2)

        #     # ret_tt+=ret_t

        #     ret.append(ret_t)

        # return ret[-1]

这个就是两种方法

一：看做二叉树，dfs遍历一遍，左右分别是括号两边，寻找的条件是左括号不超过n，有括号比左括号少，知道匹配

二：动态规划，最左边的括号一定是（，这样f(n)可以递归为 （f(i)）+f(n-1-i)