括号生成

题目

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

原题链接

解答

基于动态规划思路

选最左边的括号（必然存在与其配对的回括号）这一对括号，可以将括号组分隔成2部分：

n对括号的组合 = '('+p对括号组合+')'+q对括号组合， 其中p+q = n-1， 0 <= p <= n-1

在arr数组存放所有对数i（i < n)的排列结果，arr中每一项也都是个数组，是i对括号时的组合结果。

/**
 * @param n 
 */
function generateParenthesis(n) {
    let arr = [];
    // 初始值
    arr[0] = ['']; // 为了循环能开始
    arr[1] = ['()'];
    
    for(let i = 2; i<=n; i++) {
        let tmpArr = [];
        for(let p = 0; p<i;p++) {
            arr[p].forEach(itemP => {
                arr[i-1-p].forEach(itemQ => {
                    tmpArr.push('(' + itemP + ')' + itemQ);
                })
            })
        }
        arr.push(tmpArr);
    }
    return arr[n];
}

基于递归：回溯法

左边第一个括号必然是左括号，第二个有两种可能： 左括号 or 右括号。在括号生成过程中，为了满足有效的括号对，需要满足： 左括号&右括号数量一致。

function generateParenthesis(n) {
    let arr = [];
    
    function gen(s = '', left = 0, right = 0) {
        if(s.length === 2 * n) {
            arr.push(s);
            return;
        }
        // 兵分两路1，如果还能放左括号
        if(left < n) {
            gen(s + '(', left+1, right);
        }
        // 兵分两路2，如果可以放右括号
        if(right < left) {
            gen(s+ ')', left, right+1);
        }
    }
    gen();
    return arr;
}