面试题 08.09. 括号

面试题 08.09. 括号

括号。设计一种算法，打印 n 对括号的所有合法的（例如，开闭一一对应）组合。
说明：解集不能包含重复的子集。
例如，给出 n = 3，生成结果为：
[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]

思路

dfs 判断，优先加入左括号，然后在左括号数量大于右括号时，加入右括号，当左右括号相等时加入结果数组中。

解答

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