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

示例：

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

/**
 * 递归（回溯）
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    var arrStr = [];
    var dfs = (left, right, str) => {
        if(left == 0 && right == 0){
            arrStr.push(str);
            return;
        }
        if(left > 0){
            dfs(left-1, right, str+'(');
        }
        if(right > left){
            dfs(left, right-1, str+')');
        }
    }
    dfs(n, n, '');
    return arrStr;
};

/**
 * 动态规划
 * f(0) == ""
 * f(1) == (f(0))
 * f(2) == (f(0))f(1) + (f(1))f(0)
 * f(3) == (f(0))f(2) + (f(1))f(1) + (f(2))f(0)
 * ...
 * f(n) == ((f0))f(n-1) + (f(1))f(n-2) + (f(2))f(n-3) + ... +(f(i))f(n-i-1) + ... + (f(n-1))
 * == "(" + f(n-1)的一部分排列 +")" + f(n-1)的另一部分排列
 * == "(" + X +")" + Y
 * X 从0到n Y从到n
 * 0 代表 f(n-1)的所有情况在 另一边
 * 大于0 && 小于n 代表 f(n-1)的部分情况在最后一组括号内部 另一部分在外边
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    var dp = [['']];
    for(var i = 1; i <= n; i++){
        var result = [];
        for(var j = 0; j < i; j++){
            var first = dp[j];
            var second = dp[i-1-j];
            for(var firstTemp of first){
                for(var secondTemp of second){
                    result.push(`(${firstTemp})${secondTemp}`);
                }
            }
        }
        dp.push(result);
    }
    return dp[n];
};