---
title: "301. Remove Invalid Parentheses"
url: "https://laigary.com/interview/coding/301-remove-invalid-parentheses"
type: "note"
section: "coding"
date: "2025-11-30"
updated: "2026-07-30"
tags: ["String", "Backtrack", "Breadth-First Search"]
---

# 301. Remove Invalid Parentheses

[301\. Remove Invalid Parentheses](https://leetcode.com/problems/remove-invalid-parentheses/)

給一個含括號和字母的字串，**刪掉最少的括號**讓它變成合法的，回傳所有可能的結果（順序不拘、不能重複）。

## 思路

跟 [22. Generate Parentheses](/interview/coding/22-generate-parentheses) 是同一個規則的兩個方向：

| | 起點 | 動作 |
|---|---|---|
| [22](/interview/coding/22-generate-parentheses) | 空字串 | **加**括號，只加合法的 |
| 301 | 一個壞掉的字串 | **刪**括號，刪到合法為止 |

兩題共用同一個不變量：**從左到右讀，任何前綴裡的右括號都不能多於左括號。**

### 決策樹長什麼樣

從左到右掃每一個字元，每個**括號**都有兩個選擇：**刪掉**或**保留**。字母沒得選，一定保留。

所以決策樹的分支數是 $2^{\text{括號數}}$，這就是為什麼它是 Hard。

```text
"(()"
 │
 ├─ 刪掉 s[0] ─── ...
 └─ 保留 s[0] ─── ├─ 刪掉 s[1] ─── ...
                  └─ 保留 s[1] ─── ...
```

### 「最少」怎麼處理

這是這題比 22 多出來的難點。有兩種做法：

1. **先算出要刪幾個**，再只走「剛好刪那麼多」的分支
2. **邊走邊記錄目前最好的**，發現更好的就把舊答案全部丟掉

下面用的是第 2 種，靠三個狀態撐起來：

- `ignored` —— 這條路徑上已經刪了幾個
- `min_removed` —— 目前找到的最少刪除數
- `valid` —— 對應那個最少刪除數的所有答案

走到底時分三種情況：`ignored` 比目前最好的**更少**（找到更佳解 → 清空答案集重新開始）、**一樣**（並列 → 加進去）、**更多**（丟掉）。

而 `if ignored > min_removed: return` 這一行是剪枝：**已經刪得比最好的還多，再走下去也不可能贏**。

### 為什麼答案要用 `set`

因為**不同的刪除位置可能產生同一個字串**：

```text
"(()"  刪掉索引 0 的 '(' → "()"
       刪掉索引 1 的 '(' → "()"      ← 同一個結果
```

決策樹會把這兩條路都走一遍，但題目要的是**不重複的字串**。用 `set` 是最省事的去重方式 —— 這也是為什麼最後要 `list(valid)`。

## 解題方向

```python
from typing import List

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        min_removed = float('inf')
        valid = set()

        def backtrack(idx, left_count, right_count, curr, ignored):
            nonlocal min_removed

            # [優化] 剪枝：如果目前刪除的數量已經超過已知最小值，就不用繼續了
            if ignored > min_removed:
                return

            if idx == len(s):
                if left_count == right_count:
                    # 找到更佳解：更新最小值，並重置結果集
                    if ignored < min_removed:
                        min_removed = ignored
                        valid.clear()
                        valid.add("".join(curr))
                    # 找到同樣好的解：加入結果集
                    elif ignored == min_removed:
                        valid.add("".join(curr))
                return

            char = s[idx]

            # 情況 1: 不是括號，直接加入
            if char != '(' and char != ')':
                curr.append(char)
                backtrack(idx + 1, left_count, right_count, curr, ignored)
                curr.pop()
            else:
                # 情況 2: 是括號
                
                # 選項 A: 刪除 (Ignore) 這個括號
                backtrack(idx + 1, left_count, right_count, curr, ignored + 1)

                # 選項 B: 保留 (Keep) 這個括號
                curr.append(char)
                if char == '(':
                    backtrack(idx + 1, left_count + 1, right_count, curr, ignored)
                elif right_count < left_count:
                    # 只有在右括號數量小於左括號時，才能加入右括號 (剪枝無效狀態)
                    backtrack(idx + 1, left_count, right_count + 1, curr, ignored)
                
                curr.pop()

        backtrack(0, 0, 0, [], 0)
        return list(valid)
```

**`elif right_count < left_count` 就是 [22](/interview/coding/22-generate-parentheses) 那個條件搬過來的。** 它讓「保留一個會讓字串當場失效的右括號」這條分支根本不存在 —— 不是走完再判斷不合法，是壓根不走。

`left_count == right_count` 檢查的是**收尾時左右數量相等**。加上前面那個剪枝條件（右不超過左），兩者合起來就等價於「這個字串合法」，所以不需要另外寫驗證函式。

**只有 `curr.append` / `curr.pop` 需要回溯**，`left_count`、`right_count`、`ignored` 都是用參數傳的 —— 參數本來就是每層各自一份，不會互相污染。這是常見的取捨：**用參數傳就不用手動撤銷，但每層會多複製幾個值。**

（`char == ')'` 而且 `right_count >= left_count` 時，程式碼會 `append` 完什麼都不做再 `pop` 掉，等於白做一次。把 `curr.append(char)` 挪進兩個分支裡就能省掉，但可讀性會差一點。）

### `nonlocal` 還是 `self`

`min_removed` 和 `valid` 這兩個跨遞迴共用的狀態，常常會看到有人寫成 `self.min_removed` / `self.valid`。那樣能動，但**它是在繞開 Python 的作用域規則**，而規則其實只有一條：

| 你對外層變數做什麼 | 要不要宣告 |
|---|---|
| 只是**讀取**（`if ignored > min_removed`） | 不用 |
| **就地修改**（`valid.add(...)`、`curr.append(...)`、`valid.clear()`） | 不用 —— 名字沒有被重新綁定 |
| **重新綁定**（`min_removed = ignored`、`valid = set()`） | 需要 `nonlocal` |

所以這份程式碼裡：

- `min_removed = ignored` 是重新綁定 → **必須寫 `nonlocal min_removed`**，否則 Python 會把它當成新的區域變數，第一次讀取就 `UnboundLocalError`
- `valid` 只要改成 `valid.clear()` 而不是 `valid = set()`，就變成就地修改 → **完全不需要宣告**

漏寫 `nonlocal` 最陰險的情況是第二種變體：如果寫成 `valid = set()` 卻沒宣告，Python **不會報錯**，只是默默建了一個每層各自獨立的區域變數，外面那個 `valid` 永遠是空的 —— 回傳空答案卻找不到原因。

`nonlocal` 這個手法在 [394. Decode String](/interview/coding/394-decode-string) 和 [536](/interview/coding/536-construct-binary-tree-from-string) 的游標版也用過。

## 補充

**先算出「該刪幾個左括號、幾個右括號」可以大幅剪枝。** 掃一遍字串就能算出多餘的左右括號各有幾個，之後只走「剛好刪掉這麼多」的分支，中途發現刪過頭就直接砍掉。這樣連 `min_removed` 都不需要維護。我沒有用這個角度寫過，但那是這題常見的優化。

**也有 BFS 的解法**：把原字串當第 0 層，每一層產生「所有刪掉一個括號的字串」，一發現這一層出現合法的就把整層的合法解全收下來然後結束。它天然保證「最少」—— 因為 BFS 第一次碰到答案就是最短路徑，跟 [111. Minimum Depth](/interview/coding/111-minimum-depth-of-binary-tree) 是同一個道理。代價是每層要存下所有字串。

**括號家族**：

| 題目 | 在做什麼 |
|---|---|
| [20. Valid Parentheses](/interview/coding/20-valid-parentheses) | 驗證一個字串合不合法 |
| [22. Generate Parentheses](/interview/coding/22-generate-parentheses) | 從空的開始**生成**所有合法字串 |
| 301 | 從壞掉的**刪**到合法，而且要刪最少 |
| [32. Longest Valid Parentheses](/interview/coding/32-longest-valid-parentheses) | 找最長的合法子字串 |

四題的地基都是同一句：**前綴裡右括號不能多於左括號，而且最後要相等。** 模板見 [Backtracking 模板](/interview/coding/backtracking-template)。

## 複雜度

設 $n$ 是字串長度。

- 時間 $O(2^n \cdot n)$ — 每個括號兩個選擇，最壞情況（整串都是括號）有 $2^n$ 條路徑；每走到底還要 $O(n)$ 去 `join` 字串
- 空間 $O(n)$ — 遞迴深度是 $n$，`curr` 最長也是 $n$；答案集合另外是 $O(2^n \cdot n)$ 的最壞界

那兩個剪枝（`ignored > min_removed`、`right_count < left_count`）都不會改變最壞的量級，但在實際輸入上砍掉的分支非常多 —— 這也是為什麼 LeetCode 的 `n ≤ 25` 這個上限看起來很小卻跑得動。

**跟 [22](/interview/coding/22-generate-parentheses) 對照**：那題的下界是答案的個數（卡特蘭數），這題的答案通常只有幾個，指數成本是花在**搜尋**上而不是輸出上。同樣是回溯，一個是「非算不可」，一個是「還有優化空間」。