关于leetcode个人解题总结:LeetCode-Hot10022-括号生成

28次阅读

共计 837 个字符，预计需要花费 3 分钟才能阅读完成。

题目：

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

示例 1：
输出：n = 3
输入：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2：
输出：n = 1
输入：[“()”]

提醒：
1 <= n <= 8

思路：
对于括号的生成能够看成是对于左括号或者右括号的抉择。这样就能够转化为二叉树。如下图所示。

只是并不是每一条分支都是最终的后果。
须要恪守肯定的规定：
1. 以做括号结尾（第一位是左括号）
2. 左括号数量和右括号相等时，只能退出做括号。
3. 左括号和右括号数量都等于 n 时，退出数组。

代码如下：


/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    // 寄存后果的数组
    let res = [];
    // 遍历函数
    /**
     * @param string val 结点累计值
     * @param int left 以后节点的残余左括号数
     * @param int right 以后节点的残余右括号数
     */
    function tranverse(val, left, right) {
        // 左右括号用完就是后果，退出数组
        if(left === 0 && right === 0) {res.push(val);       
        } else if(left === 0 && right > 0) {
            // 左括号用完，只能退出右括号
            tranverse(val+')',left,right-1);
        } else if(left === right) {
             // 曾经存在的左右括号数相等，然而没有达到 n, 只能退出左括号
            tranverse(val+'(',left-1,right);
        } else if (left < right) {
             // 失常走两个分支
            tranverse(val+'(',left-1,right);
            tranverse(val+')',left,right-1);
        }
    }
    tranverse('(', n-1, n);
    return res;
};```

正文完