题解 | #括号生成#

使用一个变量记录当前结果中的左括号数量：

左括号数量为0时必须加入左括号；

否则，回溯法尝试加入左括号或者右括号；

每加入一个右括号，抵消一个左括号。

class Solution:
    def generateParenthesis(self , n: int) -> List[str]:
        # write code here
        ret = []
        def dfs(curr, num_left):
            if len(curr)==n*2:
                if num_left==0:
                    ret.append(curr[:]) # 注意拷贝
                return
            if num_left>n:
                return
            if num_left==0: # 没有左括号的时候，必须添加左括号
                dfs(curr+'(', num_left+1)
            else:
                dfs(curr+'(', num_left+1) # 尝试左括号，再撤销
                dfs(curr+')', num_left-1) # 尝试右括号
            return
        dfs('', 0)
        return ret