# 括号生成

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E4%B8%AD%E7%AD%89\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/10/pages/R5NyOzkn3qAZy7wCx1pS#中等) [![](https://img.shields.io/static/v1?label=\&message=LeetCode\&color=green\&style=flat-square)](/studies/algorithms.md#leetcode) [![](https://img.shields.io/static/v1?label=\&message=%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/10/pages/R5NyOzkn3qAZy7wCx1pS#深度优先搜索) [![](https://img.shields.io/static/v1?label=\&message=LeetCode%20Hot%20100\&color=blue\&style=flat-square)](/studies/algorithms.md#leetcode-hot-100)

> [22. 括号生成 - 力扣（LeetCode）](https://leetcode.cn/problems/generate-parentheses)

**问题简述**

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

**思路**

* 相当于对 `['(', ')']` 进行深度优先遍历；
* 通过剪枝排除无效情况；

  ![](/files/xMGbdGwEEYL92MwaCCV9)

  > [回溯算法（深度优先遍历）+ 广度优先遍历（Java） - liweiwei1419](https://leetcode.cn/problems/generate-parentheses/solution/hui-su-suan-fa-by-liweiwei1419/)

<details>

<summary><strong>Python（写法 1）</strong></summary>

```python
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        ret = []

        def dfs(l, r, tmp):
            # 非法情况（剪枝）
            if l < r or l > n:  # 已经包括 r > n
                return

            if l == r == n:
                ret.append(''.join(tmp))
                return
            
            # 先添加左括号
            tmp.append('(')
            dfs(l + 1, r, tmp)
            tmp.pop()

            # 再添加右括号
            tmp.append(')')
            dfs(l, r + 1, tmp)
            tmp.pop()

        dfs(0, 0, [])
        return ret
```

</details>

<details>

<summary><strong>Python（写法 2，写法 1 的等价写法）</strong></summary>

```python
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        ret = []

        def dfs(l, r, tmp):
            # 非法情况
            if l < r or l > n:  # 已经包括 r > n
                return

            if l == r == n:
                ret.append(''.join(tmp))
                return
            
            for c in '()':
                # 注意 l 和 r 也要回溯，这里直接传表达式可以省略这一步；
                # 同样，如果不用 tmp 数组，而是传字符串表达式，那么 tmp 的回溯也可以省略（写法3）
                # if c == '(': l += 1
                # else: r += 1
                tmp.append(c)
                dfs(l + 1 if c == '(' else l, 
                    r + 1 if c == ')' else r, 
                    tmp)
                tmp.pop()
                # if c == '(': l -= 1
                # else: r -= 1

        dfs(0, 0, [])
        return ret
```

</details>

<details>

<summary><strong>Python（写法 3，不回溯）</strong></summary>

```python
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        ret = []

        def dfs(l, r, tmp):
            # 非法情况
            if l < r or l > n:  # 已经包括 r > n
                return

            if l == r == n:
                ret.append(tmp)
                return

            for c in '()':
                # 不回溯的写法
                dfs(l + 1 if c == '(' else l, 
                    r + 1 if c == ')' else r, 
                    tmp + c)

        dfs(0, 0, '')
        return ret
```

</details>


---

# 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://imhuay.gitbook.io/studies/algorithms/problems/2022/10/leetcode0022-zhong-deng-kuo-hao-sheng-cheng.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.