日期：2026年10月7日
LeetCode 題目連結：301. Remove Invalid Parentheses
解題想法
困難題。題目給一個字串 $s$，$s$ 之中只有 $(, )$ 及小寫英文字母，如果要將 $s$ 變成合法的括號字串，最少要移除幾個括號？
這題下方有提示要用遞迴窮舉所有可能的組合。我一開始的寫法，先計算 $s$ 之中要移除的括號總數。用串列 $path$ 記錄目前已選的字元，用集合 $ans$ 儲存答案，並且定義在自訂函式 $dfs$ 之前。呼叫 $dfs$ 時代入 $idx, removed, balance$，代表正在檢查 $s[idx]$，已經移除 $removed$ 個括號，目前左括號比右括號多 $balance$ 個。如果 $idx == n$ 且 $balance == 0$，找到一組解，將 $path$ 接成字串加入 $ans$。這個寫法雖然可以過關，但是效率並不好。
後來改成計算 $s$ 之中要移除的左、右括號 $left, right$。呼叫 $dfs$ 時代入 $idx, le, ri, balance$，代表正在檢查 $s[idx]$，待移除的左括號數量 $le$，待移除的右括號數量 $ri$，目前左括號比右括號多 $balance$ 個。如果 $idx == n$ 且 $balance == 0$，找到一組解，將 $path$ 接成字串加入 $ans$。加上剪枝條件，如果剩下的部分全刪也無法消耗剩下的 $le + ri$。窮舉時先檢查是否還能移除這個括號或是可以加入這個括號才遞迴。這個寫法的效率比上一個寫法好很多。
Python 程式碼
Runtime: 1358 ms, beats 16.73%. Memory: 19.49 MB, beats 80.04%.
class Solution:
def removeInvalidParentheses(self, s: str) -> list[str]:
# 1. 計算要移除的括號數量
target, left = 0, 0 # 要移除的括號數量，待配對的 (
for c in s:
if c == '(':
left += 1
elif c == ')':
if left > 0: left -= 1
else: target += 1
target += left # 加上剩下的 (
# 定義窮舉用的 dfs 函式
n = len(s) # 長度
ans = set() # 答案
path = [] # 已選的字元
def dfs(idx, removed, balance):
# 正在檢查 s[idx]，已經移除的數量，左、右括數量差
if idx == n: # 遞迴出口
# 括號成對，移除數量等於目標值，找到一組答案
if balance == 0 and removed == target:
ans.add("".join(path))
return
# 窮舉
if s[idx] == '(': # 左括號
path.append('(')
dfs(idx + 1, removed, balance + 1) # 遞迴
path.pop() # 回溯
if removed < target: # 不選 s[idx]
dfs(idx + 1, removed + 1, balance) # 遞迴
elif s[idx] == ')': # 右括號
if balance > 0: # 可以加入右括號
path.append(')')
dfs(idx + 1, removed, balance - 1) # 遞迴
path.pop() # 回溯
if removed < target: # 不選 s[idx]
dfs(idx + 1, removed + 1, balance) # 遞迴
else: # 字母
path.append(s[idx])
dfs(idx + 1, removed, balance) # 遞迴
path.pop() # 回溯
dfs(0, 0, 0)
return list(ans)
