算法（附思维导图 + 全部解法）300题之（22）括号生成

零标题：算法（leetode，附思维导图 + 全部解法）300题之（22）括号生成

导读：

项目&作者

1 GitHub - LeetCode项目仓库

0）本项目地址： https://github.com/CYBYOB/algorithm-leetcode 。
目标、愿景：
让每个人都能拥有一定的算法能力、以应对面试中（会举一反三的同学还可以将其融入自己的肌肉和血液，甚至能够赋能于公司的业务和技术）的算法。

1）项目的根目录下的 README.md 文件，
可以帮您快速查阅每1道题的来源、难度、所有的题解方案等。

2）而每个题解（即 index.md 文件）中，
还将附带题目描述、所有的题解方案的思维导图（ .xmind 文件）、思路和技巧等。

3）每种题解方案都有详细的注释，
通过“数字步骤”将抽象的算法逻辑、
清晰和有层次的展示于您的面前。
可以说是，
开箱即用~

4）所有的题解方案都是经过作者1人之手，
故代码风格及其统一。
一旦阅读达到一定量后，
后续将大大提升您的阅读速度 —— “正所谓、量变引起质变”。

5）本人每周仍在不断的更新 —— 保证每周都有新的题目、题解方案刺激着您的神经 和 刷题欲望。
欢迎对算法感兴趣的同学加入我们的社群。
QQ群： 933919972 ；
作者QQ： 1520112971 ；
作者VX： c13227839870（可拉您进群、一起学习与交流~） 。

algorithm-leetcode - 题目总览

2 作者标签

1）“伪全栈工程师，主攻前端，偶尔写点后端”。

2）2019年的微信小程序应用开发赛 - 全国三等奖；
2019CODA比赛 - 前 17/211 强 且 荣获“优秀团队”称号 等。

3）“半自媒体人”，
在校期间、个人公众号（IT三少。新自媒体（公众号）号： 码农三少 ）
在半年内实现了0到5.8K+的粉丝增长等。

一题目描述

题目描述

二解法总览（思维导图）

思维导图

三全部解法

1 方案1

1)代码：

// 方案1 暴力法（简单而直观）。
// 1）穷举所有的组合。
// 2）接着遍历所有的组合，看其是否为有效的括号组合。
// 若 有效 ，则 保存到数组里 —— 最后将该数组返回即可。
var generateParenthesis = function(n) {
    // 递归实现。
    const dfs = (curIndex, maxIndex, curArr, resArr) => {
        // 1）递归出口。
        // 当前下标 curIndex 为 最大的下标值时，保存该组合 并 退出此时递归。
        if (curIndex === maxIndex) {
            resArr.push(curArr.join(''));
            return;
        }

        // 2）递归主体。分 2种 选择。
        // 2.1）选择 '(' ，下标加1 并 继续递归下去。 
        curArr[curIndex] = '(';
        dfs(curIndex + 1, maxIndex, curArr, resArr);
        // 2.2）选择 ')' ，下标加1 并 继续递归下去。 
        curArr[curIndex] = ')';
        dfs(curIndex + 1, maxIndex, curArr, resArr);
    }

    // 判断当前组合（ str ）是否为有效的括号组合
    const isValid = function(str) {
        // 1）初始化 相关的正则表达式 。
        const reg = /\(\)/;

        // 2）处理。
        // 核心：若 str存在 () 子串，则 将给它们不断的替换成 '' ，并 更新str值 。
        while (reg.test(str)) {
            str = str.replace(reg, '');
        }

        // 3）返回结果。
        // 若 将所有的 () 子串 都替换成 '' 后、str长度为0，则 为有效的的括号。
        return str.length === 0;
    }


    // 1）初始化相关变量
    const curIndex = 0,
        curArr = [];
    let resArr = [];

    // 2）调用定义好的 递归 函数，将所有组合存放至 数组 resArr 。
    dfs(curIndex, n * 2, curArr, resArr);

    // 3）遍历 resArr 。
    // 若 当前组合是有效的，则 将其保留下来（使用 JS 自带的 filter 函数 + 我们刚实现的 isValid 函数 ）。
    resArr = resArr.filter(item => {
        return isValid(item);
    });

    // 4）返回结果 resArr 。
    return resArr;
}

2 方案2

1)代码：

// 方案2 “回溯（含剪枝）” —— 即方案2的优化版。
// 技巧、核心：在于剪枝；相关的核心代码如下：
// if (leftNum < rightNum || leftNum > n) {
//     return;
// }
var generateParenthesis = function(n) {
    // 递归实现。
    const dfs = (leftNum, rightNum, n, curStr, resArr) => {
        // 1）递归出口
        // 1.1）优化、边界、核心：其实就是做了剪枝，因为此时继续产生的组合肯定为 非有效的。
        if (leftNum < rightNum || leftNum > n) {
            return;
        }
        // 1.2）边界：此时必为 有效的，直接将该组合 放入resArr 并 终止本次递归 即可。
        if (leftNum === rightNum && leftNum === n) {
            resArr.push(curStr);
            return;
        }

        // 2）递归主体。分 2种 选择。
        // 2.1 选择 '(' ，leftNum 加1 并 继续递归下去。 
        dfs(leftNum + 1, rightNum, n, curStr + '(', resArr);
        // 2.1 选择 ')' ，rightNum 加1 并 继续递归下去。 
        dfs(leftNum, rightNum + 1, n, curStr + ')', resArr);
    }

    // 1）初始化相关变量
    const leftNum = rightNum = 0,
        curStr = '',
        resArr = [];

    // 2）调用定义好的 dfs 函数，得到所有的有效组合（均存放在数组 resArr 里）。
    dfs(leftNum, rightNum, n, curStr, resArr);

    // 3）返回结果 resArr 。
    return resArr;
}

3 方案3

1)代码：

// 方案3 动态规划（即 DP ） - 版本1。
// 核心：dp[i][m] = "(" + dp[m -1][0...m_l] + ")" + dp[k][0...k_l]
// 其中 0 <= m < i && m + k = i - 1
// dp[i] 为 一维数组 —— 保存其所有有效的组合。
// 综上，dp[n] 为 结果数组。
var generateParenthesis = function(n) {
    // 1）状态初始化
    const dp = [];
    dp[0] = [""];
    dp[1] = ["()"];

    // 2）核心：根据递推公式处理
    for (let i = 2; i <= n; i++) {
        let resArr = [];
        for (let m = 0; m < i; m++) {
            const k = (i - 1) - m,
                arr_1 = dp[m],
                arr_2 = dp[k],
                l_1 = arr_1.length,
                l_2 = arr_2.length;

            for (let ii = 0; ii < l_1; ii++) {
                for (let jj = 0; jj < l_2; jj++) {
                    // 2.1）将所有有效的组合放入 数组 resArr 里。
                    resArr.push("(" + arr_1[ii] + ")" + arr_2[jj]);
                }
            }
        }

        // 2.2）将当前的 数组 resArr 赋值给 dp[i] 。
        dp[i] = resArr;
    }

    // 3）返回结果 dp[n] 。
    return dp[n];
}

4 方案4

1)代码：

// 方案4 动态规划（即 DP ） - 版本2。
// 技巧：遍历 dp[i - 1] 得到 curStr 。
// dp[i]此时可以加入3种情况 —— ...new Set([`(${curStr})`, `()${curStr}`, `${curStr}()`]) ，边界：需去重
// 注：未通过，可能有些情况为考虑到。
var generateParenthesis = function(n) {
    // 1）状态初始化
    const dp = [];
    dp[0] = [""];
    dp[1] = ["()"];

    // 2）核心：根据递推公式处理。
    for (let i = 1; i<= n; i++) {
        const arrPre = dp[i - 1],
            arrPreLength = arrPre.length;
        dp[i] = [];

        for (let j = 0; j < arrPreLength; j++) {
            const curStr = arrPre[j];
            // 2.1）核心：分 3种 情况，() 放2边、往左边放 + 往右边放。
            dp[i].push(...new Set([`(${curStr})`, `()${curStr}`, `${curStr}()`]));
        }
    }

    // 3）返回结果 dp[n] 。
    return dp[n];

    // 参考：
    // 1）https://leetcode-cn.com/problems/generate-parentheses/solution/dong-tai-gui-hua-by-youngluo-icyk/
}

四内推&更多

1 内推

本人是百度的1名工程师，欢迎校招、社招同学向本人投递简历。
本人可内推公司（也可帮忙内推阿里、腾讯、字节、美团、滴滴、京东等）的所有岗位，欢迎私信。

2 更多

以下是个人整理的一些笔记和书籍（永久有效链接: https://pan.baidu.com/s/1SPc3umO6cZlBtoPylSaHzw 密码: eqee ，若失效的话可私信本人（或向 “码农三少” 公众号发送 “资料” ）以进行最新资料的获取）：

理财书籍pdf
技术书籍pdf
个人基金