剑指 Offer II 085. 生成匹配的括号

剑指 Offer II 085. 生成匹配的括号

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

示例 1：
输入：n = 3 输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2：
输入：n = 1 输出：[“()”]
​

提示：

• 1 <= n <= 8

​

注意：本题与主站 22 题相同： https://leetcode-cn.com/problems/generate-parentheses/

思路

dfs 回溯法，记录当前位数已有的左右括号数量，如果相同且等同于题目给的对数 n，存入结果数组中。如果左括号或者右括号个数超过当前数 n，或者右括号数大于左括号数为非法括号字符串时，跳出递归。

解答

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  const res = [];
  let temp = [];
  const dfs = (l, r) => {
    if (l === n && r === n) {
      res.push(temp.slice().join(""));
      return;
    }
    if (l > n || r > l || r > n) return;
    temp.push("(");
    dfs(l + 1, r);
    temp.pop();
    temp.push(")");
    dfs(l, r + 1);
    temp.pop();
  };
  dfs(0, 0);
  return res;
};