22. 括号生成

[Geekhyt]

原题链接

回溯法

题目要求我们生成所有可能的有效的括号组合，数字 n 代表生成括号的对数。

使用回溯法进行解题，从空字符串开始构造，做加法。

1. 当 l < r 时(构造用的左括号 < 构造用的右括号)，不满足条件，直接剪枝。
2. 当 l < n 时，可以一直插入左括号，最多插入 n 个。
3. 当 r < l (构造用的右括号 < 构造用的左括号)时，可以插入右括号。

const generateParenthesis = function (n) {
    const res = []
    function generate(l, r, str) {
        // 递归终止条件
        if (l === n && r === n) {
            return res.push(str)
        }
        if (l < r) {
            return
        }
        if (l < n) {
            generate(l + 1, r, str + '(')
        }
        if (r < l) {
            generate(l, r + 1, str + ')')
        }
    }
    generate(0, 0, '')
    return res
}

• 时间复杂度：O(2^n)
• 空间复杂度：O(2^n)