301. Remove Invalid Parentheses

──────────────────────────────────────────────────────────────────────

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

思路

跟 22. Generate Parentheses 是同一個規則的兩個方向：

	起點	動作
22	空字串	加括號，只加合法的
301	一個壞掉的字串	刪括號，刪到合法為止

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

決策樹長什麼樣

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

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

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

「最少」怎麼處理

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

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

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

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

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

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

為什麼答案要用 `set`

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

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

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

解題方向

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 那個條件搬過來的。 它讓「保留一個會讓字串當場失效的右括號」這條分支根本不存在 —— 不是走完再判斷不合法，是壓根不走。

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 和 536 的游標版也用過。

補充

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

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

括號家族：

題目	在做什麼
20. Valid Parentheses	驗證一個字串合不合法
22. Generate Parentheses	從空的開始生成所有合法字串
301	從壞掉的刪到合法，而且要刪最少
32. Longest Valid Parentheses	找最長的合法子字串

四題的地基都是同一句：前綴裡右括號不能多於左括號，而且最後要相等。 模板見 Backtracking 模板。

複雜度

設 $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 對照：那題的下界是答案的個數（卡特蘭數），這題的答案通常只有幾個，指數成本是花在搜尋上而不是輸出上。同樣是回溯，一個是「非算不可」，一個是「還有優化空間」。

301. Remove Invalid Parentheses

思路

決策樹長什麼樣

「最少」怎麼處理

為什麼答案要用 set

解題方向

nonlocal 還是 self

補充

複雜度

為什麼答案要用 `set`

`nonlocal` 還是 `self`