# LeetCode: 301. 删除无效的括号¶

## 1、题目描述¶

输入: "()())()"



输入: "(a)())()"



输入: ")("



## 2、解题思路¶

• 首先从左只有扫描一遍，找出需要删除的最小数量的左括号和右括号
• 然后从右向左扫描，找出当前位置需要的左括号的数量（如果当前位置左括号数量已经超过右括号，跳出）
• 采用回溯法，从第一个位置开始，尝试进行左右括号的删除操作
• 当删除的左右括号数量等于最少删除数量时，判断两个拼接的字符串是否
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
ans = set()
length = len(s)
left_del = 0
right_del = 0
for c in s:
if c == "(":
left_del += 1
if c == ")":
if left_del:
left_del -= 1
else:
right_del += 1
right_no_remove = [float('-inf')] * len(s)
right_right = 0
for i in range(length - 1, -1, -1):
if s[i] == ")":
right_right += 1
if s[i] == "(":
if right_right:
right_right -= 1
else:
break
right_no_remove[i] = right_right

def dfs(pos, left_bracket_num, left_d, right_d, cur_s):
if left_d == left_del and right_d == right_del:
if pos >= length:
if left_bracket_num == 0:
else:
if left_bracket_num == right_no_remove[pos]:
else:
if pos >= length:
return
if s[pos] == "(":
dfs(pos + 1, left_bracket_num + 1, left_d, right_d, cur_s + s[pos])
if left_d < left_del:
dfs(pos + 1, left_bracket_num, left_d + 1, right_d, cur_s)
elif s[pos] == ")":
if right_d < right_del:
dfs(pos + 1, left_bracket_num, left_d, right_d + 1, cur_s)
if left_bracket_num:
dfs(pos + 1, left_bracket_num - 1, left_d, right_d, cur_s + s[pos])
else:
dfs(pos + 1, left_bracket_num, left_d, right_d, cur_s + s[pos])

dfs(0, 0, 0, 0, "")
return list(ans)