题目 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]
题解
- 1.使用暴力枚举的方法列出所有的生成括号的情况然后，通过判断 isvalid 来将结果添加到result中
class Solution: def generateParenthesis(self, n: int) -> List[str]: def generate(A): if len(A) == 2*n: if valid(A): ans.append("".join(A)) else: A.append('(') generate(A) A.pop() A.append(')') generate(A) A.pop() def valid(A): bal = 0 for c in A: if c == '(': bal += 1 else: bal -= 1 if bal < 0: return False return bal == 0 ans = [] generate([]) return ans
时间复杂度： O（2^2n * n）
空间复杂度：O（n）
2.
class Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] def generate(left, right, n, s): if left == n and right == n: res.append(s) if left < n: generate(left+1, right, n, s + '(') if right < left: generate(left, right + 1, n, s +')') generate(0, 0, n, '') return res
这种办法为回溯 + 剪枝的方法，通过条件排除了右括号多余左括号的情况
时间复杂度： O(N)
空间复杂度： O(N)
