Heading

22.括号生成 (opens new window)

Tags: algorithms google uber zenefits string backtracking

Langs: c cpp csharp dart elixir erlang golang java javascript kotlin php python python3 racket ruby rust scala swift typescript

• algorithms
• Medium (77.60%)
• Likes: 3532
• Dislikes: -
• Total Accepted: 807.1K
• Total Submissions: 1M
• Testcase Example: '3'

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

 

示例 1：

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

示例 2：

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

 

提示：

• 1 <= n <= 8

/*
 * @lc app=leetcode.cn id=22 lang=javascript
 *
 * [22] 括号生成
 */

// @lc code=start
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const res = []
    const dfs = (lRemain, rRemain, str) => {
        if (str.length === 2 * n) {
        res.push(str)
        return
        }
        if (lRemain > 0) {
        dfs(lRemain - 1, rRemain, str + '(')
        }
        if (rRemain > lRemain) {
        dfs(lRemain, rRemain - 1, str + ')')
        }
    }
    dfs(n, n, '')
    return res
}
// @lc code=end