leetcode中如何实现括号生成

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

class Solution:    def generateParenthesis(self, n: int) -> List[str]:        if n is None or n < 1:            return []        res = []        # 递归，左右括号的数量        '''        def helper(s, l, r):            if l == 0 and r == 0:                res.append(s)            if l > 0:                helper(s+'(', l-1, r)            if r > l:                helper(s+')', l, r-1)            if r > l:                return         helper('', n, n)        return res        '''        # dp        # 状态转移方程：dp[i] = '(' + dp[j] + ')' + dp[i-j-1]   # 由两部分组成        # dp[i]表示i对括号的有效括号组合        dp = [None] * (n+1)        dp[0] = ['']        for i in range(1, n+1):            cur = []            for j in range(i):                left = dp[j]                right = dp[i-j-1]                for s1 in left:                    for s2 in right:                        cur.append('(' + s1 + ')' + s2)            dp[i] = cur        return dp[n]