Generate Parentheses

The number n represents the number of parentheses to be generated. Please design a function that can generate all possible and valid combinations of parentheses.

Example

Input: n = 3 Output: [ "((()))", "(()())", "(())()", "()(())", "()()()" ]

Solution

/**
 * @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);
}

Idea

Use backtracking. In the code above, startCount represents the number of left parentheses, endCount represents the number of right parentheses, str is the cached string, target is the target array, and n is the number of pairs of parentheses. During the recursion, when startCount is less than n, add ( to the cached string and increase startCount by 1, then pass the updated parameters to the next recursion. When endCount is less than startCount, add ) to the cached string and increase endCount by 1, then pass the updated parameters to the next recursion. When the length of the string is equal to n*2, the recursion ends and the cached string is added to the target array.

Daily Question

https://github.com/WindrunnerMax/EveryDay

Source

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