題目

給出 n 代表生成括號的對數(shù)，請你寫出一個函數(shù)，使其能夠生成所有可能的并且有效的括號組合。

例如，給出 n = 3，生成結(jié)果為：

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

原題鏈接

解答

基于動態(tài)規(guī)劃思路

選最左邊的括號（必然存在與其配對的回括號）這一對括號，可以將括號組分隔成2部分：

n對括號的組合 = '('+p對括號組合+')'+q對括號組合， 其中p+q = n-1， 0 <= p <= n-1

在arr數(shù)組存放所有對數(shù)i（i < n)的排列結(jié)果，arr中每一項也都是個數(shù)組，是i對括號時的組合結(jié)果。

/**
 * @param n 
 */
function generateParenthesis(n) {
    let arr = [];
    // 初始值
    arr[0] = ['']; // 為了循環(huán)能開始
    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 右括號。在括號生成過程中，為了滿足有效的括號對，需要滿足： 左括號&右括號數(shù)量一致。

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;
}