leetcode22. 括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        s=''
        res=[]
        left=right=n
        self.helper(s, res, left, right)
        return res

    # 二叉树的广度优先？
    def helper(self,s,res,left,right):
        '''
        :param s: str
        :param res: List[str]
        :param left: int64
        :param right: int64
        :return: list
        '''
        # 空节点暂停遍历
        if left==0 and right==0:
            res.append(s)
        # 遍历左子树。条件：左括号剩余可添加个数>0。
        if left>0:
            self.helper(s+'(',res,left-1,right)
        # 遍历右子树。
        # 添加了一个左括号才能添加右括号。所以right>left。
        if right>left:
            self.helper(s+')',res,left,right-1)