括号生成

发表于 | 分类于 |
字数统计: 447 字 | 阅读时长 ≈ 1 分钟

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

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

示例 2：
输入：n = 1
输出：[“()”]

回溯

  • 选择
    • 在这里，每次最多两个选择，选左括号或右括号，“选择”会展开出一棵解的空间树。
    • 用 DFS 遍历这棵树，找出所有的解，这个过程叫回溯。
  • 约束条件
    • 即，什么情况下可以选左括号，什么情况下可以选右括号。
    • 利用约束做“剪枝”，即，去掉不会产生解的选项，即，剪去不会通往合法解的分支。
      • 比如()，现在左右括号各剩一个，再选)就成了())，不能让这个错的选择成为选项（不落入递归）：
1
2
3
if (right > left) { // 右括号剩的比较多，才能选右括号
    dfs(str + ')', left, right - 1);
}
  • 目标
    • 构建出一个用尽 n 对括号的合法括号串。
    • 意味着，当构建的长度达到 2*n，就可以结束递归（不用继续选了）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var generateParenthesis = function (n) {
  const res = [];

  const dfs = (lRemain, rRemain, str) => { // 左右括号所剩的数量，str是当前构建的字符串
    if (str.length == 2 * n) { // 字符串构建完成
      res.push(str);           // 加入解集
      return;                  // 结束当前递归分支
    }
    if (lRemain > 0) {         // 只要左括号有剩，就可以选它，然后继续做选择（递归）
      dfs(lRemain - 1, rRemain, str + "(");
    }
    if (lRemain < rRemain) {   // 右括号比左括号剩的多，才能选右括号
      dfs(lRemain, rRemain - 1, str + ")"); // 然后继续做选择（递归）
    }
  };

  dfs(n, n, ""); // 递归的入口，剩余数量都是n，初始字符串是空串
  return res;
};