ericpuwang

括号生成

https://leetcode.cn/problems/generate-parentheses/description/

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

示例1

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

示例2

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

提示

• 1 <= n <= 8

解题思路

当n=3时, 有效括号: ((())),(()()),(())(),()(()),()()() n对括号，则左右括号数分别为n,即左右括号总数为max_value=2n. 先尝试放置左括号，放置条件：左括号数目小于max_value//2; 再尝试放置右括号，放置条件是右括号数目小于左括号。终止条件：当前括号数等于括号总数

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        self.res = []
        self.backstracking("", 0, 0, 2*n)
        return self.res

    def backstracking(self, current: str, left: int, right: int, max_value: int) -> None:
        # 递归终止, 找到一种有效括号
        if len(current) == max_value:
            self.res.append(current)
            return

        # 左括号的数目小于max_value//2
        if left < max_value // 2:
            current += '('
            self.backstracking(current, left+1, right, max_value)
            current = current[:-1]
        # 右括号数目小于左括号数目
        if right < left:
            current += ')'
            self.backstracking(current, left, right+1, max_value)
            current = current[:-1]