22. [✔][M]括号生成

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

---

题解：

括号问题

/*
 * @lc app=leetcode.cn id=22 lang=typescript
 *
 * [22] 括号生成
 */

// @lc code=start
function generateParenthesis(n: number): string[] {
    let res: string[] = [];

    // left和right为可用数量

    const backtrack = (left: number, right: number, track: string[]) => {
        if (right < left) return;
        if (left < 0 || right < 0) return;
        if (left === 0 && right === 0) {
            res.push(Array.from(track).join(""));
            return;
        }

        track.push("(");
        backtrack(left - 1, right, track);
        track.pop();

        track.push(")");
        backtrack(left, right - 1, track);
        track.pop();
    }

    backtrack(n, n, []);

    return res;
};
// @lc code=end