前往此题

解题思路

这里以树的形式可以很巧妙的解这道题

我们以n = 2为例：

我们以n作为左右括号的剩余个数，用数的形式进行组合，排除掉非有效括号后，剩余的都是有效括号。

在这里我们有几点需要注意：

1. 由于括号的规则，只要还存在左括号，右边随便加什么都行，反之则不行。
2. 左右括号都为0的时候则结算
3. 由第一点我们可以展开，产生右括号的时候右括号的数量必须大于左括号。

代码

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res, cur = [], ''

        def dfs(cur, left, right):
            if left == 0 and right == 0: 
                res.append(cur)
                return
            if right < left: return
            if left > 0:
                dfs(cur + '(', left - 1, right)
            if right > 0:
                dfs(cur + ')', left, right - 1)
        
        dfs(cur, n, n)
        return res