括号.md

面试题 08.09. 括号

https://leetcode-cn.com/problems/bracket-lcci/

题目描述

括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。

说明：解集不能包含重复的子集。

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

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

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

思路

dfs
先建立二叉树
然后搜索
计算
当left>n 或者 right>left，跳出循环
如果left=right==n,那么就将当前路径加入到path中

python代码

执行用时： 36 ms , 在所有 Python3 提交中击败了 90.72% 的用户 内存消耗： 15.1 MB , 在所有 Python3 提交中击败了 46.68% 的用户

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