22.括号生成.md

22. 括号生成

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

解题思路

可以把需要生成的括号想象成一棵二叉树的遍历，每一个节点的左儿子值是“（”，右儿子值是“）”。当遍历的路径长度为2n时得到一个结果，然后回溯到上一个节点值为“（”的节点即可，比如说得到 “（（（）））”的结果后回溯到“ （（”时即可，然后接着遍历得到“（（）（））”，再回溯到“（（）”，然后接着遍历得到“（（））（）”。

代码实现

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
    const result = [];
    // leftNum左括号数量 rightNum右括号数量 paths 当前存储的括号
    function dfs(leftNum, rightNum, paths) {
        if (paths.length === 2 * n) {
            result.push(paths.join(''));
        }
        if (leftNum < n) {
            paths.push('(');
            dfs(leftNum + 1, rightNum, paths);
            paths.pop();
        }
        if (rightNum < leftNum) {
            paths.push(')');
            dfs(leftNum, rightNum + 1, paths);
            paths.pop();
        }
    }
    dfs(0, 0, [])
    return result;
};