括号生成

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

示例

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

题解

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    var target = [];
    dfs(0, 0, "", target, n);
    return target;
};

function dfs(startCount, endCount, str, target, n){
    if(str.length === n*2) {
        target.push(str);
        return 0;
    }
    if(startCount < n) dfs(startCount + 1, endCount, str + "(", target, n);
    if(endCount < startCount) dfs(startCount, endCount + 1, str + ")", target, n);
}

思路

使用回溯法,上述代码中startCount代表左括号的数量,endCount代表右括号的数量,str是缓存字符串,target是目标数组,n是括号对数数量。当进行递归时,判断在左括号数量startCount数量小于n的情况下,可以在缓存字符串加入(并将startCount + 1然后传递参数进行下一次递归,在右括号的数量少于左括号的情况下,那么可以在缓存字符串中加入)并将endCount + 1然后传递参数进行下一次递归,当字符串的长度等于n*2时结束递归并将缓存字符加入目标数组。

每日一题

https://github.com/WindrunnerMax/EveryDay

题源

https://leetcode-cn.com/problems/generate-parentheses/