0022. 括号生成【中等】

• 1. 🔗 links
• 2. 📝 Description
• 3. 💻 题解.1 - 回溯算法

1. 🔗 links

• https://leetcode.cn/problems/generate-parentheses/solutions/418884/shou-hua-tu-jie-gua-hao-sheng-cheng-hui-su-suan-fa/
  • 「手画图解」从 22. 括号生成 看回溯算法的三个要点

2. 📝 Description

leetcode

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

3. 💻 题解.1 - 回溯算法

var generateParenthesis = function (n) {
  const ans = [];

  const dfs = (lRemain, rRemain, str) => {
    if (str.length === n * 2) {
      ans.push(str);
      return;
    }

    if (lRemain > 0) dfs(lRemain - 1, rRemain, str + '(');
    if (rRemain > lRemain) dfs(lRemain, rRemain - 1, str + ')');
  }

  dfs(n, n, "");
  return ans;
};

• 
  • from: 「手画图解」从 22. 括号生成 看回溯算法的三个要点
  • 该图片来自参考题解，图片中标注的顺序，是 dfs 依次入栈的次序。
  • 图片中标注的顺序，是 dfs 依次入栈的次序。
• 已选：str
• 可选：由 lRemain 和 rRemain 决定
• 结束：str.length === n * 2
• 回溯的套路中，难点通常在于确定「可选」是什么，「已选」、「结束」往往都很容易明确。