22. 括号生成

[swiftwind0405]

方法一：回溯法

解题思想：
利用回溯法，不断地往前一个结果的尾部追加左括号或者右括号。

代码：

var generateParenthesis = function(n) {
    const arr = [];
    function generate(left, right, str) {
        // 递归终结条件：n 都用完了
        if (left === n && right ===n) {
            arr.push(str);
            return;
        }

        // 如果左括号没用完（第一肯定先使用左括号），就继续递归
        if(left < n) {
            generate(left + 1, right, str + '(');
        }

        // 如果右括号没用完（右括号肯定比左括号少，且有括号没用完），就继续递归
        if(right < left) {
            generate(left, right + 1, str + ')')
        }
    }

    generate(0, 0, '');
    return arr;
};

复杂度分析：

• 时间复杂度：这个不会分析，可以见这里括号生成官方解法方法二的说明。
• 空间复杂度：O(n)，除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 O(1) 的空间，最多递归 2n 层，因此空间复杂度为 O(n)。

方法二：动态规划

自己还没实现，后面补
参考sl1673495/leetcode-javascript#31