leetcode100括号生成
目录
【leetcode100】括号生成
1、题目描述
数字
n
代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且
有效的
括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]2、初始思路
2.1 思路
全排列+筛选
2.2 犯错点
全排列，时间复杂度高，且易读性较差
3 优化算法
3.1 思路
在构造的过程中直接确保括号的正确匹配：
- 当左括号数量<n时，可以继续添加左括号；
- 当右括号数量<左括号数量时，才可以添加右括号。
3.2 代码
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
path = []
def backtracking(path, left, right):
if len(path) == 2*n:
res.append(''.join(path.copy()))
return
if left<n:
path.append('(')
backtracking(path, left+1, right)
path.pop()
if right<left:
path.append(')')
backtracking(path, left, right+1)
path.pop()
backtracking(path, 0, 0)
return res