LeetCode 22. 括号生成

题目

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

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

方法：暴力解法

• result 记录所有符合题目的组合

generate 函数：生成所有组合方式

• 若某个组合 list 的长度等于最终生成的括号数量，即表示该组合已完成。调用 valid 函数判断该组合是否符合有效，若有效，将其转化成字符串的形式并存入 result

• 若某个组合 list 的长度不等于最终生成的括号数量，即表示该组合未完成。调用 generate 函数并将左括号/右括号加入

  
  
  举例 非完整

valid 函数：判断括号组合是否有效

• balance 表示左括号的数量减去右括号的数量
• 遍历该括号数组 list
  • 若此时的括号为左括号，那么 balance 加一；否则，balance 减一
  • 若 balance 小于零，即表示此时右括号数量多于左括号数量，那么一定无法得到有效组合，返回 False
• 根据 balance 与零的关系返回结果

class Solution(object):
    def generateParenthesis(self, n):
        def generate(list):
            if len(list) == 2 * n:
                if valid(list):
                    result.append(''.join(list))
            else:
                list.append('(')
                generate(list)
                list.pop()
                list.append(')')
                generate(list)
                list.pop()

        def valid(list):
            balance = 0
            for i in list:
                if i == '(':
                    balance += 1
                else:
                    balance -= 1
                if balance < 0:
                    return False
            return balance == 0

        result = []
        generate([])
        return result

参考

代码相关：https://leetcode.cn/problems/generate-parentheses/solution/gua-hao-sheng-cheng-by-leetcode-solution/