求star

题目#

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

题解:key:#

①暴力递归#

TIP

​ 想象有2*n个位置，根据题意，每个位置都可以放置(或)，则只需要穷举出所有目标长度的序列，然后筛选出符合条件的序列即可

如何判断序列是否可行:

1. 右括号数量 <= 左括号数量 (例如”())“,接下去如何排列都不可行)
2. 左括号数量 <= n && 右括号数量 <= n (题目规定n代表生成括号的对数)

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
    let res = []
    findAll([], 0, res, n)
    return res
};
let findAll = (cur, len, res, n) => {
    if (len === 2 * n) {
        if (Valid(cur)) {
            res.push(cur.join(''))
        }
    } else {
        // 每一个位置都有两种选择
        cur[len] = '('
        findAll(cur,len+1,res,n)
        cur[len] = ')'
        findAll(cur,len+1,res,n)
    }
}
// 验证序列是否符合题目要求
let Valid = (cur) => {
    let cnt = 0
    for (let c of cur) {
        if (c === '(') {
            ++cnt
        } else {
            --cnt
        }
        if (cnt < 0) return false // 说明')'数目大于'('数目,不符合条件
    }
    return cnt === 0 // 左右括号数是否相等
}

②回溯法（DFS）#

TIP

参考题解: https://leetcode.cn/problems/generate-parentheses/solution/shou-hua-tu-jie-gua-hao-sheng-cheng-hui-su-suan-fa/

核心思想就是不断选择，每次选择都只有两种可能，所有的’选择’会展开一颗解的空间树

约束条件(具体原因在上一种题解已经说明)：

• 只要’(‘有剩，就可以选
• 剩余’)‘需要大于剩余’(‘才可选’)’

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const res = []

    const dfs = (lRemain,rRemain,curStr) => {
        if(curStr.length == 2 * n) {
            res.push(curStr)
            return
        }
        // 只要左括号有剩，就可以选它，然后继续做选择（递归）
        if(lRemain > 0 ){
            dfs(lRemain - 1 , rRemain,curStr + '(')
        }
        // 右括号比左括号剩的多，才能选右括号
        if(rRemain > lRemain){
            dfs(lRemain,rRemain-1,curStr+')')
        }
    }
    dfs(n,n,'')
    return res
};