乐趣区

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

22. 括号生成

题目:

数字 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;
};```
退出移动版