22. 括号生成——medium-回溯

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

示例：

输入：n = 3
输出：[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses

思路：

• 用open表示左括号数，close表示右括号数
• 当open < n 时，还可继续添加左括号
• 当close < open时，左侧必有一个或多个左括号还未匹配，此时可以添加右括号，
• 递归结束后将括号移除，即回溯

复杂度分析：（抄自官方题解）

var generateParenthesis = function (n) {
    let res = [];
    let ans = [];
    function find(open, close, max) {
        if (res.length === max * 2) {
            ans.push(res.join(""));
            return;
        }
        if (open < max) {
            res.push("(");
            find(open + 1, close, max);
            res.pop();
        }
        if (close < open) {
            res.push(")");
            find(open, close + 1, max);
            res.pop();
        }
    }
    find(0, 0, n);
    return ans;
};