22. 括号生成

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

示例 1：

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

示例 2：

输入：n = 1
输出：["()"]

提示：
1 <= n <= 8

Python 解答：

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def dfs(string, n, i, j):
            if i > n  or j > n or j > i:
                return 
            elif i == j and i == n:
                res.append(string)
                return 
            for q in range(2):
                if q == 0:
                    dfs(string+'(', n, i+1, j)
                else:
                    dfs(string+')', n, i, j+1) 
        dfs("", n, 0, 0)        
        return res