[22] 括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

这道题可以用递归来解，本质上就是一次二叉树的深度优先遍历。难点关键在于如何剪枝，减少不必要的递归次数。我们可以发现，

1. 当左括号或右括号剩余个数<0时，明显不合法，剪掉。
2. 若每次增加括号的过程中，若剩余的左括号的数量大于剩余的右括号，则当前递归一定是不合法的，直接剪掉。
3. 若左括号和右括号同时正好用完时，则可生成合法字符串，加入到res数组中。

我们还能继续做出优化。实际上当左括号已经用完的时候，剩下的就只有右括号一种了，其后面的判断也可以直接剪掉了，直接将剩下的所有右括号全部加入进当前字符串后即可生成合法字符串了。

var generateParenthesis = function(n) {
  const res = [];
  backtrack('', n, n);
  return res;

  function backtrack(str, left, right) {
    if (left < 0 || right < 0 || left > right) return;
    if (left === 0) {
      str += ')'.repeat(right);
      res.push(str);
      return;
    }

    backtrack(str + '(', left - 1, right);
    backtrack(str + ')', left, right - 1);
  }
};

换个角度想，括号问题可以看做一个特殊的全排列，当左右括号数都等于n时，输出结果。只是要求当前子串下，右括号的个数不能多于左括号。

于是题解也可以改成这样。

function generateParenthesis(n: number): string[] {
  const res: string[] = [];
  backtrack('', 0, 0);
  return res;

  function backtrack(str: string, left: number, right: number) {
    if (left === n && right === n) {
      res.push(str);
    }
    left < n && backtrack(str + '(', left + 1, right);
    right < left && backtrack(str + ')', left, right + 1);
  }
}