Leetcode刷题(第22题)——括号的生成

x33g5p2x  于2022-02-28 转载在 其他  
字(0.7k)|赞(0)|评价(0)|浏览(272)

一、题目

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

二、示例

示例 1:
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

示例 2:
输入:n = 1
输出:["()"]

三、思路
本题中,由于n的数量不确定,但是我们可以知道括号字符串在拼接的过程中一定满足的条件是:左括号的数量一定大于等于右括号的数量。当拼接结束后需要满足的条件时左括号的数量等于右括号的数量,并且左括号的数量加上右括号的数量一定等于2 * n
在递归过程中,加上左括号的条件是:左括号的数量小于n,并且左括号的数量一定大于等于右括号的数量
加入右括号的条件是:右括号的数量小于左括号的数量
四、代码

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
    const result = []
    const func = (str, left, right) => {
        if (str.length === 2 * n) {
            result.push(str)
            return
        }
        if (left < n && left >= right) {
            func(str + "(", left + 1, right)
        }
        if (left > right) {
            func(str + ")", left, right + 1)
        }
    }
    func("", 0, 0)
    return result
};

五、总结

相关文章