# 0022. 括号生成

### 题目地址(22. 括号生成)

<https://leetcode-cn.com/problems/generate-parentheses>

### 题目描述

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

示例：

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

```

### 前置知识

* DFS
* 回溯法

### 公司

* 阿里
* 百度
* 腾讯
* 字节

### 思路

本题是 [20. 有效括号](/leetcode-solution/easy/20.valid-parentheses.md) 的升级版。

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

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

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

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

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

伪代码：

```py
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，CPP

JS Code:

```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:

```py
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
```

CPP Code:

```cpp
class Solution {
private:
    vector<string> ans;
    void generate(int leftCnt, int rightCnt, string &s) {
        if (!leftCnt && !rightCnt) {
            ans.push_back(s);
            return;
        }
        if (leftCnt) {
            s.push_back('(');
            generate(leftCnt - 1, rightCnt, s);
            s.pop_back();
        }
        if (rightCnt > leftCnt) {
            s.push_back(')');
            generate(leftCnt, rightCnt - 1, s);
            s.pop_back();
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        string s;
        generate(n, n, s);
        return ans;
    }
};
```

**复杂度分析**

* 时间复杂度：O(2^N)
* 空间复杂度：O(2^N)

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/8kgn2o.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/22.generate-parentheses.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.