22. 括号生成

Difficulty
Medium
Tags
回溯
DFS
URL
https://leetcode-cn.com/problems/generate-parentheses/
Star
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足：左括号必须以正确的顺序闭合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
  • 1 <= n <= 8

法1 回溯法

思路
可以采用暴力回溯，每个字符都单独试验过去，需要试验2n个字符，然后当当前路径的字符长度达到2n时，单独判断一下是否为有效括号。如果是就添加到结果中。
观察有效的括号可以发现：任何时候，如果右括号数目大于左括号数目，则一定无效。将这一条规则添加到回溯的过程中，就可以避免所有的不合法括号了。也就是不用单独函数判断生成的路径括号是否合法了。
题解
# 暴力回溯
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        self.res = []
        self.dfs(path='', n=2*n)
        return self.res

    def dfs(self, path, n):
        if len(path) == n and self.isValid(path):
            self.res.append(path)
            return
        if len(path) >= n:
            return

        self.dfs(path+'(', n)
        self.dfs(path+")", n)

    def isValid(self, path):
        if path[0] == ')':
            return False

        stack = []
        i = 0
        while i < len(path):
            if path[i] == '(':
                stack.append('(')
            else:
                if len(stack) == 0:
                    return False
                stack.pop()
            i += 1
        return False if stack else True

# -------剪枝优化-----------#
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        self.res = []
        self.dfs(path='', left=0, right=0, n=n)
        return self.res

    def dfs(self, path, left, right, n):
        if left == n and right == n:
            self.res.append(path)
            return
				# 如果右括号数目多于左括号，那么一定是无效的。
        # 这一条加在遍历的过程中，可以避免掉所有的非法括号
        if right > left or left > n or right > n:
            return

        self.dfs(path+'(', left+1, right, n)
        self.dfs(path+")", left, right+1, n)