22. 括号生成

[mengjian-github]

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

 

示例 1：

输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"] 示例 2：

输入：n = 1 输出：["()"]

[mengjian-github]

这个题目考察的是回溯算法，一般我们根据回溯算法枚举出所有括号的可能性，然后判断每一种可能性是否合法，在这里合法的条件是： 从左往右来看，左括号的个数必须大于右括号，且左括号的个数不能超过n。

可以把这个条件放在回溯算法的生成中来提升运行效率：

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const result = [];

    function backTrace(path = [], openLen = 0, closeLen = 0) {
        if (path.length === n * 2) {
            // 已经生成了一组解法
            result.push(path.join(''));
            return;
        }

        if (openLen < n) {
            path.push('(');
            backTrace(path, openLen + 1, closeLen);
            path.pop();
        } 

        if (closeLen < openLen) {
            path.push(')');
            backTrace(path, openLen, closeLen + 1);
            path.pop();
        }
    }

    backTrace();

    return result;
};