数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
codeType
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
codeType
输入：n = 1
输出：["()"]
提示：
- 1 <= n <= 8
解法
解法一
ts
function generateParenthesis(n: number): string[] {
const res = []
const stackBack = (path: string, left: number, right: number) => {
/**
path: 结果序列
left: 左括号数量
right: 右括号数量
*/
if(left === right && left + right === n * 2){
res.push(path)
return
}
// 下一步只有两种。添加左括弧或者添加右括弧
if(left < n){
// 左括号数量一定要大于等于右括弧
stackBack(path + '(', left + 1, right)
}
if(right < n && right < left){
stackBack(path + ')', left, right + 1)
}
}
stackBack('', 0, 0)
return res
};
解法二
解法一中的path虽然是基础类型，但是每次栈都是重新创建的也需要很大的开销，可以用数组替代，然后在栈回退时回溯数组，从而减少内存开销。（不过这是理论上的，实际测试下来还是解法一性能更好）
ts
function generateParenthesis(n: number): string[] {
const res = []
const path: string[] = []
const stackBack = (left: number, right: number) => {
/**
path: 结果序列
left: 左括号数量
right: 右括号数量
*/
if(left === right && left + right === n * 2){
res.push(path.join(''))
return
}
// 下一步只有两种。添加左括弧或者添加右括弧
if(left < n){
path.push('(')
stackBack(left + 1, right)
path.pop() // 回溯
}
// 左括号数量一定要大于等于右括弧
if(right < n && right < left){
path.push(')')
stackBack(left, right + 1)
path.pop()
}
}
stackBack(0, 0)
return res
};