数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足：左括号必须以正确的顺序闭合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
- 1 <= n <= 8
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一解
使用回溯法：
- 退出条件：左右括号数量等于 n*2 ，把其追加到 res 中，。
- 递推工作：增加左括号，直到左括号数量达到 n ，增加右括号，直到右括号数量与左括号相同。
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def backtrack(s, left, right):
if left + right == n*2:
res.append("".join(s))
return
if left < n:
s.append("(")
backtrack(s, left + 1, right)
s.pop()
if right < left:
s.append(")")
backtrack(s, left, right + 1)
s.pop()
res = []
backtrack([], 0, 0)
return res
- 时间复杂度 $O(\frac{4^{n}}{\sqrt{n}})$：时间复杂度与卡特兰数有关。
- 空间复杂度：O(n)：最多递归 2n 层，因此空间复杂度为 O(n)。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/generate-parentheses/solution/gua-hao-sheng-cheng-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。