Lt22.括号生成、回溯算法

22. 括号生成

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

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

思路

设置一个递归函数，传入当前括号字符串，已有的左括号数及右括号数。
如果左括号数等于右括号数等于 0，说明已经是一个有效的括号组合字符串，将字符串结果加入结果数组中，进行回溯。
如果左括号数等于右括号数，为了括号有效，下一个必须是左括号，所以字符串传入左括号，同时传入 left-1。
如果左右不相等，优先深度，先判断 left 是否大于 0，优先添加左括号。

解答

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  const res = [];
  const generate = (str, left, right) => {
    if (left === 0 && right === 0) {
      res.push(str);
      return;
    }
    if (left === right) generate(str + "(", left - 1, right);
    else {
      if (left > 0) generate(str + "(", left - 1, right);
      generate(str + ")", left, right - 1);
    }
  };
  generate("", n, n);
  return res;
};