# \[22]\[中等]\[回溯]\[BFS] 括号生成

## 题目描述

[22. 括号生成](https://leetcode-cn.com/problems/generate-parentheses/)

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

示例：

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

## 解题思路

### 回溯

回溯算法的基本思想是: 从一条路往前走, 能进则进, 不能进则退回来, 换一条路再试.

这道题即递归地增加括号, 每次增加有两种选择, 左括号和右括号. 当然每种需要满足一定的条件才能增加, 否则这条路是堵死的:

* 左括号: 左括号的数量小于$$n$$时都可以增加
* 右括号: 首先要求右括号的数量同样要小于$$n$$, 而且同是要已有的右括号的数量要小于左括号的数量, 两者同时满足时才能增加

回溯需要一个停止条件, 本题的停止条件很明显, 当前生成的字符串长度等于$$n\*2$$就需要停止了, 停止后, 将这个字符串加入到最后的结果列表中.

```python
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def gen(current, unused, used, result):
            if unused == 0 and used == n:
                result.append(current)

            if unused > 0:
                gen(current + '(', unused - 1, used, result)
            if used + unused < n and used < n:
                gen(current + ')', unused, used + 1, result)
            return result
        res = []
        gen('', n, 0, res)
        return res
```


---

# 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://kerasnoone.gitbook.io/garnet/suan-fa/hui-su/22-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.