经典题解-回溯法和动态规划

题目

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


示例：
输入：n = 3
输出：[
      “((()))”,
      “(()())”,
      “(())()”,
      “()(())”,
      “()()()”
    ]

解法

回溯法

判断回溯很简单，拿到一个问题，你感觉如果不穷举一下就没法知道答案，那就可以开始回溯了。


一般回溯的问题有三种：

• Find a path to success 有没有解
• Find all paths to success 求所有解
  • 求所有解的个数
  • 求所有解的具体信息
• Find the best path to success 求最优解

回溯法是一个剪枝了的二叉树。我们要得到的结果是可以 good leaf，如果不满足 good leaf 就继续向下搜索，搜索的时候需要满足一定的条件。





从上面的图片中我们可以很明显的看到，最后五条画黑线的就是最终的结果，其中左分支都是添加左括号，右分支都是添加右括号。


那么我们在什么情况下添加左括号呢？很明显，最多能添加 n 个左括号，在递归调用的时候，在能传递到最底层的共用字符串中先添加 ”(“ ，然后 left-1，递归调用就可以。
那什么时候添加右括号呢？当左括号个数大于右括号的个数时添加右括号。


总之，向下搜索要满足两个条件：

• 插入数量不超过n
• 可以插入 ） 的前提是 ( 的数量大于 ）

回溯法的代码套路是使用两个变量： res 和 path，res 表示最终的结果，path 保存已经走过的路径。如果搜到一个状态满足题目要求，就把 path 放到 res 中。


代码后面的判断条件都是 if，而不是 elif，因为是满足两个条件的任意一个就可以继续向下搜索，而不是同时只能满足其中的一个。

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
  // 保存所有有效路径
  let res = [];
  dfs(res, n, n, '');
  return res;
};

function dfs(res, left, right, path) {
  if (right === 0) {
    return res.push(path);
  }
  if (left > 0) {
    dfs(res, left - 1, right , path + '(');
  }
  if (right > left) {
    dfs(res, left, right - 1 , path + ')');
  }
}

动态规划

什么是动态规划？在此题中，动态规划的思想类似于数学归纳法，当知道所有 i<n 的情况时，我们可以通过某种算法算出 i=n 的情况。

dp递推公式：
dp[i]="("+dp[m]+")"+dp[k]
其中m+k=i-1

本题最核心的思想是，考虑 i=n 时相比 n-1 组括号增加的那一组括号的位置。


当我们清楚所有 i<n 时括号的可能生成排列后，对与 i=n 的情况，我们考虑整个括号排列中最左边的括号。
它一定是一个左括号，那么它可以和它对应的右括号组成一组完整的括号 “( )”，我们认为这一组是相比 n-1 增加进来的括号。


那么，剩下 n-1 组括号有可能在哪呢？


剩下的括号要么在这一组新增的括号内部，要么在这一组新增括号的外部（右侧）。
既然知道了 i<n 的情况，那我们就可以对所有情况进行遍历：


“(“ + 【i=p时所有括号的排列组合】 + “)” + 【i=q时所有括号的排列组合】
其中 p + q = n-1，且 p q 均为非负整数。
事实上，当上述 p 从 0 取到 n-1，q 从 n-1 取到 0 后，所有情况就遍历完了。


注：上述遍历是没有重复情况出现的，即当 (p1,q1)≠(p2,q2) 时，按上述方式取的括号组合一定不同。

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  const cache = [];
  cache[0] = [""];
  cache[1] = ["()"];
  for (let i = 2; i <= n; i++) {
    const temp = [];
    for (let j = 0; j < i; j++) {
      const list1 = cache[j];
      const list2 = cache[i - 1 - j];
      for (let k1 of list1) {
        for (let k2 of list2) {
          temp.push("(" + k1 + ")" + k2);
        }
      }
    }
    cache.push(temp);
  }
  return cache[n];
};

原文链接：[https://leetcode-cn.com/problems/generate-parentheses/solution/zui-jian-dan-yi-dong-de-dong-tai-gui-hua-bu-lun-da/](https://leetcode-cn.com/problems/generate-parentheses/solution/zui-jian-dan-yi-dong-de-dong-tai-gui-hua-bu-lun-da/)
原文链接：[https://leetcode-cn.com/problems/generate-parentheses](https://leetcode-cn.com/problems/generate-parentheses)
原文链接：[https://leetcode-cn.com/problems/generate-parentheses/solution/ru-men-ji-bie-de-hui-su-fa-xue-hui-tao-lu-miao-don/](https://leetcode-cn.com/problems/generate-parentheses/solution/ru-men-ji-bie-de-hui-su-fa-xue-hui-tao-lu-miao-don/)