每天一道leetcode(Day 16)

22. 括号生成

题目描述

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

示例

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

解题思路

看到这种符合某种规律，但又有区别的算法问题，自然想到递归的解法。
观察可得：

1. 某一次递归终止时需要将当前字符存入数组
2. 字符任取一个位置左侧必为左括号 >= 右括号(因此字符串中需要插入右括号的时机为 (right < left)
3. 每次递归除了需要传当前字符还需要记清当前左右括号数

代码

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  let res = [];
  //  cur :当前字符  left：当前字符左括号 right:当前字符右括号
  const help = (cur, left, right) => {
    if (cur.length === 2 * n) {
      res.push(cur);
      return;
    }
    if (left < n) {
      help(cur + "(", left + 1, right);
    }
    if (right < left) {
      help(cur + ")", left, right + 1);
    }
  };
  help("", 0, 0);
  return res;
};

参考

22. 括号生成