T22 括号生成

题目链接：leetcode-cn.com/problems/ge…

思路一：DFS搜索

朴素解法

这是一道典型的「DFS搜索」题目，与之前我们学习过的「电话号码的字母组合」类似，但这里我们会分析得更细致一些。

对于此类题目，为了便于入手，我们不妨先不考虑任何优化，只考虑如下几个问题：

1. 搜索的起点在哪里？
2. 如何进行搜索？
3. 每一个搜索节点下有几条分支？
4. 如何判断一条搜索路径是否结束？

对于问题(1)，由题意我们知道，想要形成闭合的括号组合，最左侧的括号必须是(，这就是我们的起点。

对于问题(2)，我们只需要从最左侧出发，逐位搜索（实际上是枚举）可能的所有情况即可。

对于问题(3)，由于我们这里先不考虑优化，因此每个搜索节点下只有两条分支（即两种可能性）：(、)。

对于问题(4)，根据本题题意我们知道，如果要结束一条搜索路径，无非是碰到了两种情况：①发现搜索到了正确答案；②发现再往下搜索不可能得到正确答案。

我们先考虑前者。

为了表述方便，我们不妨记已搜索到的(数量为leftNum，已搜索到的)为rightNum。

很显然，只有当leftNum == rightNum == n时，才说明已经找到了正确的答案。

“等等！仅仅保证左右括号数量相等还不够，还需要保证它们能够一一闭合才对啊！”，如果你现在心中有这个疑惑，非常棒。但请不要着急，先让我们分析后者。

什么时候再往下不可能得到正确答案呢？

首先，题目已经规定了答案中括号对的个数n，也就是说，倘若我们对每个答案枚举的字符个数超过n * 2（下记作totalNum）却发现其不是正确答案，那么该路径必然需要结束。

其次，为了使得所有的括号对都有闭合的机会，必须保证搜索过程中始终有leftNum ≥ rightNum。

这个条件稍稍有点难度，如果有同学想不明白的话，不妨用「反证法」：

假设leftNum < rightNum，表明已搜索到的左侧区域必定有多余的)存在，而此时无论我们如何在右侧区域添加括号（即继续往下搜索），都不可能使前面多余的)闭合。因此此时搜索到的结果肯定不是正确答案！

现在相信你已经解开了刚才的疑惑。是的，我们只要在搜索的中途将括号无法闭合的情况予以排除，就不需要在校验最终正确答案的时候考虑这个问题了！

现在我们已经分析清楚了这四个问题，下面直接运用我们的老朋友「递归」来实现「DFS搜索」就行了。由于代码比较简单，这里不再仔细讲解。如果你是初次接触此类题目的同学，请尝试找一找刚才的四个问题分别对应代码的哪一部分。

代码如下：

function generateParenthesis(n) {
    const ansArr = [];
    dfs(n * 2, 1, 0, '(', ansArr);
    return ansArr;
}
function dfs(totalNum, leftNum, rightNum, ans, ansArr) {
    if (totalNum === leftNum + rightNum) {
        leftNum === rightNum && ansArr.push(ans);
    }
    else if (leftNum >= rightNum) {
        dfs(totalNum, leftNum + 1, rightNum, ans + '(', ansArr);
        dfs(totalNum, leftNum, rightNum + 1, ans + ')', ansArr);
    }
}

剪枝优化

我们刚才已经编写出了完全不带任何优化的版本，下面我们尝试对其进行「剪枝优化」。

什么是「剪枝优化」呢，从字面上理解，就是在搜索的过程中及时发现并"剪去"搜索树上不可能抵达正确答案的"枝条"。

换句话说，就是我们需要在搜索过程中对一些具体情况进行研判，使得我们尽可能走可能抵达正确答案的搜索路径，规避不可能抵达正确答案的路径。

首先是我们很容易想到的两种情况：

• 当leftNum = rightNum时，答案中下一个字符必须是(；
• 当leftNum + rightNum = totalNum - 1时，答案中下一个字符必须是).

还要其他可以进行剪枝的情况吗？

答案是肯定的。别忘了我们之前分析过，如果要找到正确答案，必须保证搜索过程中不等式leftNum ≥ rightNum始终成立。那么反过来说，如果走某一条路径会打破这个不等式，那么搜这个路径一定不会得到正确答案！

根据上面的分析，我们优化的代码如下：

function generateParenthesis(n) {
    const ansArr = [];
    //注意：现在这里若写dfs(n * 2, 0, 0, '', ansArr);也是可以的
    //思考：为什么？
    dfs(n * 2, 1, 0, '(', ansArr);
    return ansArr;
}
function dfs(totalNum, leftNum, rightNum, ans, ansArr) {
    if (totalNum === leftNum + rightNum) {
        leftNum === rightNum && ansArr.push(ans);
    }
    //思考：为什么先前代码中的条件leftNum >= rightNum已不再需要？
    else {
        if (leftNum === rightNum) {
            dfs(totalNum, leftNum + 1, rightNum, ans + '(', ansArr);
        } else if (leftNum + rightNum === totalNum - 1) {
            dfs(totalNum, leftNum, rightNum + 1, ans + ')', ansArr);
        } else {
            leftNum + 1 >= rightNum && dfs(totalNum, leftNum + 1, rightNum, ans + '(', ansArr);
            leftNum >= rightNum + 1 && dfs(totalNum, leftNum, rightNum + 1, ans + ')', ansArr);
        }
    }
}

拓展：从代数角度理解

下面我们来提一下如何从代数角度来理解本题中「DFS搜索」的实现。

我们可以记出现一个(为得+1分，出现一个)为得-1分。那么对于符合题意的括号组合，都有：

• 当搜索到最终结果时，有总分score = 0，即leftNum = rightNum. 且搜索深度deep = n * 2，即leftNum + rightNum = totalNum；
• 在搜索过程中，总分始终满足0 ≤ score ≤ n，即leftNum ≥ rightNum且leftNum ≤ n

这两条结论与我们上文中对题意的分析是完全吻合的。

代码如下：

function generateParenthesis(n) {
    const ansArr = [];
    dfs(n * 2, 1, 1, '(', ansArr);
    return ansArr;
}
function dfs(maxDeep, deep, score, ans, ansArr) {
    if (deep === maxDeep) {
        score === 0 && ansArr.push(ans);
    } else {
        if (score === 0) {
            dfs(maxDeep, deep + 1, score + 1, ans + '(', ansArr);
        } else if (deep === maxDeep - 1) {
            dfs(maxDeep, deep + 1, score - 1, ans + ')', ansArr);
        } else {
            score + 1 <= maxDeep/2 && dfs(maxDeep, deep + 1, score + 1, ans + '(', ansArr);
            score - 1 >= 0 && dfs(maxDeep, deep + 1, score - 1, ans + ')', ansArr);
        }
    }
}

思路二：DP动态规划

从观察开始

下面我们思考一个问题：这道题可以用「动态规划」进行解答吗？

我们知道，如果一道题可以用「动态规划」进行解答，那么题目中必须蕴含着某种递推关系。

如果你还没有任何头绪的话，我们可以先来观察一下使用前面「DFS搜索」获得的几组正确答案：

请留意：是不是当n比较大时的答案，看上去像n比较小时的答案组装起来的？

为了进一步发掘其中的规律，我们来举一个具体的例子分析一下。

比如当n = 4时的一个答案'(()())()'。为了更好地观察，我们拆开来看：'( ()() ) ()'。

现在一切就很明显了，这个答案看上去应该是在一组新增加的括号内塞了n = 2时的一个答案()()，又再它的外面加了n = 1时的一组答案。我们知道1 + 2 + 1 = 4，这便是这个n = 4答案的由来！

递推关系

类似上面的例子还有很多。通过对它们的分析，我们寻找的递推关系也就呼之欲出了：

若规定dp[n]表示当括号对总数为n时的任意一个答案，

则有dp[n] = "(" + dp[p] + ")" + dp[q]，其中p + q + 1 = n.

代码实现

利用递推关系，我们只需逐一计算从1到n - 1的所有正确答案，便能够得到括号对为n时的答案——因为对每一个dp[n]中的答案，它都是由前面的dp[n - 1]中的答案递推（也就是所谓的"组装"）出来的！

代码如下：

function generateParenthesis(n) {
    /* 初始化dp数组 */
    const dp = [['']];
    for(let i = 1; i <= n; i++) dp[i] = [];
    /* 动归核心部分 */
    for(let curN = 1; curN <= n; curN++) {
        for(let p = 0; p < curN; p++) {
            let q = curN - p - 1;
            //由于dp[n]中可能包含了多个答案，
            //所以别忘了需要对其逐个进行遍历。
            for(let inside of dp[p]) {
                for(let outside of dp[q]) {
                    dp[curN].push("(" + inside + ")" + outside);
                }
            }
        }
    }
    /* 返回所求结果 */
    return dp[n];
}

写在文末

我是来自在校学生编程兴趣小组江南游戏开发社的PAK向日葵，我们目前正在致力于开发自研的非营利性网页端同人游戏《植物大战僵尸：旅行》，以锻炼我们的前端应用开发能力。

我们诚挚邀请您体验我们的这款优秀作品，如果您喜欢TA的话，欢迎向您的同事和朋友推荐。如果您有技术方面的问题希望与我们探讨，欢迎直接与我联系。您的支持是我们最大的动力！