LeetCode 022. 括号生成

题目描述

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

示例：

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

难度：Middle

前置知识

DFS
回溯法

公司

阿里
百度
腾讯
字节

Js中文网 – 前端进阶资源教程 www.javascriptC.com,typescript 中文文档
Javascript中文网是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js……等，以帮助开发者成长为愿景的社区

思路

本题是 20. 有效括号的升级版。

由于我们需要求解所有的可能，因此回溯就不难想到。回溯的思路和写法相对比较固定，并且回溯的优化手段大多是剪枝。

不难想到，如果左括号的数目小于右括号，我们可以提前退出，这就是这道题的剪枝。比如 ())....，后面就不用看了，直接退出即可。回溯的退出条件也不难想到，那就是：

左括号数目等于右括号数目
左括号数目 + 右括号数目 = 2 * n

由于我们需要剪枝，因此必须从左开始遍历。（WHY？）

因此这道题我们可以使用深度优先搜索(回溯思想)，从空字符串开始构造，做加法，即 dfs(左括号数, 右括号数目, 路径)，我们从 dfs(0, 0, ”) 开始。

伪代码：

res = []
def dfs(l, r, s):
   if l > n or r > n: return
   if (l == r == n): res.append(s)
   # 剪枝，提高算法效率
   if l > r: return
   # 加一个左括号
   dfs(l + 1, r, s + '(')
   # 加一个右括号
   dfs(l, r + 1, s + ')')
dfs(0, 0, '')
return res

由于字符串的不可变性，因此我们无需撤销 s 的选择。但是当你使用 C++ 等语言的时候，就需要注意撤销 s 的选择了。类似：

s.push_back(')');
dfs(l, r + 1, s);
s.pop_back();

关键点

当 l < r 时记得剪枝

代码

语言支持：JS，Python3

JS Code:

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：前端中文网是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js
 * @param {number} n
 * @return {string[]}
 * @param l 左括号已经用了几个
 * @param r 右括号已经用了几个
 * @param str 当前递归得到的拼接字符串结果
 * @param res 结果集
 */
const generateParenthesis = function (n) {
  const res = [];

  function dfs(l, r, str) {
    if (l == n && r == n) {
      return res.push(str);
    }
    // l 小于 r 时不满足条件 剪枝
    if (l < r) {
      return;
    }
    // l 小于 n 时可以插入左括号，最多可以插入 n 个
    if (l < n) {
      dfs(l + 1, r, str + "(");
    }
    // r < l 时 可以插入右括号
    if (r < l) {
      dfs(l, r + 1, str + ")");
    }
  }
  dfs(0, 0, "");
  return res;
};

Python Code:

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def dfs(l, r, s):
            if l > n or r > n: return
            if (l == r == n): res.append(s)
            if l < r: return
            # 加一个左括号
            dfs(l + 1, r, s + '(')
            # 加一个右括号
            dfs(l, r + 1, s + ')')
        dfs(0, 0, '')
        return res

复杂度分析