括号生成

问题简述

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。
例如，给出n=3，解集为：
"((()))", "(()())", "(())()", "()()()", "()(())"

括号生成_牛客题霸_牛客网

思路：递归+回溯

• 关键是中止条件的判断，详见代码；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return string字符串一维数组
#
class Solution:
    def generateParenthesis(self , n: int) -> List[str]:
        # write code here
        
        ret = []
        tmp = []
        
        def dfs(i, j):
            if i > n or j > n or i < j:
                return
            
            if i == j == n:
                ret.append(''.join(tmp))
                return
            
            tmp.append('(')
            dfs(i + 1, j)
            tmp.pop()
            
            tmp.append(')')
            dfs(i, j + 1)
            tmp.pop()
        
        dfs(0, 0)
        return ret