---
title: "22. Generate Parentheses"
url: "https://laigary.com/interview/coding/22-generate-parentheses"
type: "note"
section: "coding"
date: "2023-01-27"
updated: "2026-07-30"
tags: ["String", "Backtrack", "Classic"]
---

# 22. Generate Parentheses

[22. Generate Parentheses](https://leetcode.com/problems/generate-parentheses/)

給 `n`，列出所有由 `n` 對括號組成的**合法**組合。

## 思路

這一題和 [46. Permutations](/interview/coding/46-permutations) 很類似，題目要求的就是要窮舉。

最好寫回溯法的題目通常都會符合人類的直覺。括號的特性是左括號跟右括號一定成雙成對出現，所以這題就是不斷地先把左括號放完、再放右括號，之後退回一個左括號，再往下繼續拼湊。以 3 對括號為例，產生的順序如下：

```text
1. ((()))
2. (()())
3. (())()
4. ()(())
5. ()()()
```

### 兩個條件就決定了一切

終止條件很直接：**當左右括號都用滿 `n` 個時**，就是產生出一組可行解了，記錄到答案裡。

至於這一步要放左括號還是右括號，只有兩條規則：


| 規則             | 意思                |
| -------------- | ----------------- |
| `left < n`     | 左括號還沒用完就可以放       |
| `right < left` | **右括號的數量不能超過左括號** |


第二條是整題的核心。它其實就是括號合法性的定義：**從左到右讀，任何一個前綴裡「已關閉的」都不能多於「已開啟的」**，否則就會出現 `)` 找不到對應的 `(`。

跟 [20. Valid Parentheses](/interview/coding/20-valid-parentheses) 對照著看就很清楚 —— 那題是拿這個規則去**驗證**一個字串，這題是拿同一個規則去**生成**。

這個題目比較需要想的是回溯解法通常會有一個遞迴，在這個題目，左括號跟右括號各要進行一次遞迴。

### 剪枝在這題不是優化，是解法本身

一般的回溯題常常是「先窮舉、再篩掉不合法的」。這題如果那樣做，就是列出所有 $2^{2n}$ 種 `(` `)` 的排列再逐一驗證 —— 而合法的只佔極小一部分：

```text
n = 4    合法解 14 個     所有排列 256 種     只有 5.5% 合法
n = 8    合法解 1430 個   所有排列 65536 種   只有 2.2% 合法
```

比例還會隨 `n` 越變越糟。而 `left < n` 和 `right < left` 這兩個條件讓遞迴**從頭到尾只走進合法的分支** —— 走到底的每一條路都是答案，一個都不用丟掉。

這就是 [Backtracking 模板](/interview/coding/backtracking-template) 說的「剪枝是唯一能救時間複雜度的手段」最乾淨的例子：**它把「生成後過濾」變成「只生成合法的」。**

## 解題方向

```python
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def backtrack(curr = [], left = 0, right = 0):
            if left == n and right == n:
                ans.append(''.join(curr))
                return
            if left < n: # left can not exceeds n
                curr.append('(')
                backtrack(curr, left + 1, right)
                curr.pop()
            if right < left: # right can not exceeds left
                curr.append(')')
                backtrack(curr, left, right + 1)
                curr.pop()

        backtrack()
        return ans
```

`curr.append(...)` 和 `curr.pop()` 就是回溯的「做選擇 / 撤銷選擇」。`curr` 是**路徑的性質**，離開這條分支就得還原 —— 跟 [46](/interview/coding/46-permutations) 的 `used[i] = False`、[207](/interview/coding/207-course-schedule) 的 `on_path.remove(...)` 是同一件事。

`ans.append(''.join(curr))` 一定要 `join` 成新字串（等於複製一份）。直接 `ans.append(curr)` 會把同一個 list 的參考存進去，後面的 `pop` 會把已經存好的答案改掉。這是回溯題最常見的坑。

**兩個 `if` 是平行的不是 `elif`** —— 同一層要先試左括號、再試右括號，這兩條分支都要走。也因為左括號永遠先試，輸出天然就是字典序（`(` 排在 `)` 前面）。

## 補充

**終止條件可以更短**：`if len(curr) == 2 * n` 跟 `left == n and right == n` 等價 —— 因為 `right ≤ left ≤ n`，總長度到 `2n` 時只可能是兩邊都滿。原本的寫法比較直白，兩種都行。

**合法括號組合的數量是卡特蘭數**：

$$C_n = \frac{1}{n+1}\binom{2n}{n}$$

```text
n:   1   2   3   4    5    6     7     8
個數: 1   2   5   14   42   132   429   1430
```

這個數列在很多「配對 / 巢狀」的計數問題裡都會出現（二元樹的形狀數、出入棧的序列數）。知道它的存在，主要的用處是**估複雜度時知道答案本身就有指數多個**。

**相關題**：[20. Valid Parentheses](/interview/coding/20-valid-parentheses)（驗證一個字串合不合法）、[32. Longest Valid Parentheses](/interview/coding/32-longest-valid-parentheses)（找最長的合法子字串）、[301. Remove Invalid Parentheses](/interview/coding/301-remove-invalid-parentheses)（刪最少的括號讓字串合法）。共同的骨架都是那個「前綴裡右括號不能多於左括號」的計數規則。

模板與其他回溯題見 [Backtracking 模板](/interview/coding/backtracking-template)。

## 複雜度

先講結論：**這題不可能比** $O(4^n / \sqrt{n})$ **快，因為答案本身就有那麼多個。**

- 時間 $O\left(\dfrac{4^n}{\sqrt{n}}\right)$ — 卡特蘭數 $C_n$ 約是 $\dfrac{4^n}{n^{1.5}\sqrt{\pi}}$，每個答案還要花 $O(n)$ 去 `join`，相乘之後是 $O(n \cdot C_n)$
- 空間 $O(n)$ — 遞迴深度是 $2n$，`curr` 最長也是 $2n$；輸出的 `ans` 不計

（原本這裡寫成 $O(n)$ 是錯的 —— 那是「印出一個答案」的成本，不是「產生全部答案」的成本。**只要題目要求「列出所有解」，時間下界就是解的個數**，回溯法幾乎都是這種形狀。）

**這題的剪枝救不了量級，但救了常數**：不剪枝是 $2^{2n} = 4^n$，剪枝後是 $4^n/\sqrt{n}$ —— 差的是一個多項式因子。真正的意義在於「每一條走到底的路都是答案」，中間沒有任何白工。