题目
给出 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;
}
