22.括号生成)
题目
数字n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例 1：
输入：n = 3输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1输出：["()"]
提示：
1 <= n <= 8
思路
“选与不选”：对于每一个左括号都有选或不选，对于每一个右括号都有选或不选，很明显的递归思路
1.递归终止条件：如果选的括号总数 == 2 * n，那么找到一个组合（在递归时使用剪枝，保证所有到达终止条件的组合都合法），存进答案
2.递归单层逻辑：选择左括号的数量 < n，则可以继续选，即处理下一个左括号；选择右括号的数量要 < 左括号的数量，则可以继续选，即处理下一个右括号
3.递归参数：由第二步可知，我们需要知道此时的括号组合、左括号的数量、右括号的数量
代码
class Solution: def generateParenthesis(self, n: int) -> List[str]: temp = "" res = [] def backtrack(temp,l, r): if len(temp) == 2 * n: # 找到一个组合 res.append(temp) return if l < n: # 如果左括号 < n，继续加入左括号，左括号数量+1，递归 backtrack(temp + '(', l + 1, r) if r < l: # 如果右括号 < 左括号数量，可以加入右括号，右括号数量 + 1，递归 backtrack(temp + ')', l, r + 1) backtrack("", 0, 0) return res
