腾讯&leetcode22：括号生成

[sisterAn]

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

示例：

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

leetcode地址

[oxyzhg]

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
  let str = "";

  const addBrackets = target => {
    if (target.length === n * 2) return [target]; // 递归结束条件

    let result = [];

    let matchedStart = target.match(/\(/g);
    let matchedEnd = target.match(/\)/g);
    let matchedStartCount = matchedStart ? matchedStart.length : 0; // 左边已经出现的 `(` 个数
    let matchedEndCount = matchedEnd ? matchedEnd.length : 0;

    /**
     * 下一位字符一定是开始括号的几种情况：
     * 1. 空字符串
     * 2. 开始括号数量等于闭合括号数量
     */
    if (target.length === 0 || matchedStartCount === matchedEndCount) {
      return [...result, ...addBrackets(target + "(")];
    }

    if (target.length === n * 2 - 1 || matchedStartCount === n) {
      return addBrackets(target + ")");
    }

    /**
     * 左边已出现的开始括号个数
     * 1. 如果小于n，表明未来还可新增新的成对括号
     * 2. 如果大于等于n，表明未来不会再新增成对括号
     */
    if (matchedStartCount < n) {
      result = [...result, ...addBrackets(target + "(")];
    }

    result = [...result, ...addBrackets(target + ")")];

    return result;
  };

  return addBrackets(str);
};

尝试解题失败，这写法执行时间和消耗内存挺高。记录下过程，等看看大家有什么好的解题思路。

[dinjufen]

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    let res = [];
    let path = [];
    traverse(n, n, path);
    function traverse(left, right, path) {
        if (left < 0 || right < 0) {
            return;
        }
        if (right < left) {
            return;
        }
        if (left === 0 && right === 0) {
            res.push(path.join(''));
            return;
        }
        path.push('(');
        traverse(left-1, right, path);
        path.pop();

        path.push(')');
        traverse(left, right-1, path);
        path.pop();
    }
    return res;
};

[huangruoliang]

    let res = []
    const back = (path,left,right) => {
        if(path.length === n *2 ) {
            res.push(path)
            return 
        }
        if(left > 0) {
            back(path+ '(',left-1,right)
        }
        if(right > left) {
            back(path+ ')',left,right-1)
        }
    }
    back('',n,n)
    return res
};

[sisterAn]

解答：回溯算法（深度优先遍历）

算法策略： 回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。深度优先搜索利用的就是回溯算法思想。

对应于本题，我们可以每次试探增加 ( 或 ) ，注意：

• 加入 ( 的条件是，当前是否还有 ( 可以选择

• 加入 ) 的时候，受到 ( 的限制，如果已选择的结果里的 ( 小于等于已选择里的 ) 时，此时是不能选择 ) 的，例如如果当前是 () ，继续选择 ) 就是 ()) ，是不合法的

代码实现：

const generateParenthesis = (n) => {
    const res = []
    const dfs = (path, left, right) => {
        // 肯定不合法，提前结束
        if (left > n || left < right) return
        // 到达结束条件
        if (left + right === 2 * n) {
            res.push(path)
            return
        }
        // 选择
        dfs(path + '(', left + 1, right)
        dfs(path + ')', left, right + 1)
    }
    dfs('', 0, 0)
    return res
}

复杂度分析（来源leetcode官方题解）：

leetcode