22. 括号生成

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

示例：

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

思路--深度优先遍历

当前左右括号都有大于 0个可以使用的时候，才产生分支；
产生左分支的时候，只看当前是否还有左括号可以使用；
产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以产生分支；
在左边和右边剩余的括号数都等于 0的时候结算。

image.png

python3解法

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def dfs(left, right, combination):
            if left == 0 and right == 0:
                ans.append(combination)
            if left > 0:
                dfs(left - 1, right, combination + "(")
            if right > left:
                dfs(left, right - 1, combination + ")")
        ans = []
        if n == 0 : return []
        dfs(n, n, "")
        return ans
        

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。