【leetcode】22. 括号生成（js实现）

1. 题目

22. 括号生成

2. 思路

3. 代码实现

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    let res = []
    function dfs(leftR, rightR, str) {
        // 左右括号剩下的数量，str为当前构建的字符串
        if (str.length == 2 * n) {
            res.push(str)
            return 
        }
        if (leftR > 0) {
            // 左括号有剩余，选择并递归
            dfs(leftR - 1, rightR, str + '(')
        }
        if (leftR < rightR) {
            // 右括号多于左括号的数量时，才可以选择右括号
            dfs(leftR, rightR - 1, str + ')')
        }
    }
    dfs(n, n, '') // 递归入口
    return res
};

4. 参考

「手画图解」从 22. 括号生成 看回溯算法的三个要点