かっこの生成Python

nは括弧を生成する対数を表します.可能なすべての有効な括弧の組み合わせを生成できるように関数を書いてください.
たとえば、n=3が与えられ、結果は次のようになります.
[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/generate-parentheses著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
左かっこが終わっていない場合は左かっこ、右かっこが左かっこより少ない場合は右かっこがいっぱいになると格納されます

def generateParenth(n):
    ans = []
    
    def backtrack(S='', left=0, right=0):
        if len(S) == 2*n:
            ans.append(S)
            return
        if left

括弧の生成もカトラン数を満たすもので、例えば3組の括弧の構成を生成し、2組の括弧の生成が得られたと仮定すると、3組目の括弧は先に置くことができ、そのうち0組、1組、2組、対応する右側に2組、1組、0組を置くことができる.

class Solution:
    def generateParenthesis(self, n):
        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=n-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]
s = Solution()
print(len(s.generateParenthesis(5)))
    
v = [0]*1000
v[0]=1
v[1]=1
for i in range(2, 5+1):
    for j in range(i):
        v[i] += v[j]*v[i-j-1]
print(v[5])