数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：

  1. 输入：n = 3
  2. 输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

  1. 输入：n = 1
  2. 输出：["()"]

提示：

  • 1 <= n <= 8

    解法一：回溯

    1. function generateParenthesis(n: number): string[] {
    2. let res: Array<string> = []
    4. if (n === 0) {
    5.   return res
    6. }
    8. const recursion = (cur: string, left: number, right: number) => {
    9.   if (left === 0 && right === 0) {
    10.     res.push(cur)
    11.     return
    12.   }
    14.   if (left > right) {
    15.     return
    16.   }
    17.   if (left > 0) {
    18.     recursion(cur + "(", left - 1, right)
    19.   }
    20.   if (right > 0) {
    21.     recursion(cur + ")", left, right - 1)
    22.   }
    23. }
    25. recursion("", n, n)
    26. return res
    27. };