LeetCode题解：22. 括号生成，递归生成同时过滤，JavaScript，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/generate-parentheses/

解题思路：

1. 使用递归生成成对括号。
2. 判断括号是否成对的方法如下
   • 由于括号必须成对，因此最终左右括号的数量都为括号的对数，即只要左右括号的对数小于对数，即可插入括号。
   • 只有左括号大于右括号时，才可以插入右括号。此时保证了左括号会优先插入，也就保证了括号是成对的。而且右括号的数量自然也小于对数。
3. 当字符串长度等于对数*2时，表示字符串已生成完毕，可以存入结果并终止递归。

// 使用递归生成成对括号
function generate(str, left, right, max, result) {
  // 递归终结条件
  // 当生成的字符串长度等于最大长度时结束循环
  if (str.length === max * 2) {
    // 由于字符串生成时已经进行了括号成对的判断，此处只需要存储结果
    result.push(str);
    // 结束递归
    return;
  }

  // 当前层的递归逻辑以及继续递归。
  // 当左括号小于对数时，表示可以继续生成一对括号
  // 此时先增加一个左括号。右括号可以再下一次递归补齐。
  // 同时左括号数量加1
  if (left < max) {
    generate(str + '(', left + 1, right, max, result);
  }

  // 当左括号数量大于右括号时，表示可以补充右括号组成一对括号
  // 同时右括号数量加1
  if (left > right) {
    generate(str + ')', left, right + 1, max, result);
  }
}
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  let result = []; // 储存结果

  // 使用递归生成成对括号
  generate(
    '', // 初始字符串为空
    0, // 左括号计数
    0, // 右括号计数
    n, // 括号对数
    result, // 储存结果
  );

  return result;
};