好的，我们来看 LeetCode 第 301 题：“删除无效的括号”。

题目描述

给你一个由若干括号和字母组成的字符串 s，请你通过删除最少数量的无效括号，使得输入字符串变得有效。返回所有可能的结果（可以按任意顺序返回）。

有效字符串需满足：

1. 左括号 '(' 和右括号 ')' 必须是匹配的。
2. 每个右括号 ')' 都必须有一个对应的左括号 '('。
3. 每个左括号 '(' 也必须有一个对应的右括号 ')'。

注意： 字符串中可能包含除括号 '(' 和 ')' 之外的字符（小写字母）。

示例 1：
输入：s = "()())()"
输出：["(())()","()()()"]

示例 2：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

示例 3：
输入：s = ")("
输出：[""]

解题思路（循序渐进）

这个问题看似复杂，但我们可以通过一步步分析来找到解决方案。

第一步：理解问题的核心

我们的目标是删除最少数量的无效括号，使得字符串有效。这意味着：

1. 我们不知道具体要删除哪些括号。
2. 可能有多组不同的删除方案，都能得到有效的字符串，并且删除的括号数量都是最少的。我们需要找到所有这样的方案。

关键点： 如何判断一个字符串需要删除多少括号才能变得有效？
我们可以通过一次遍历来计算出需要删除的最少左括号数和右括号数。

第二步：计算最少需要删除的左右括号数

我们定义两个计数器：

• lRemove：记录最少需要删除的多余左括号的数量。
• rRemove：记录最少需要删除的多余右括号的数量。

遍历字符串 s：

1. 遇到 '('：左括号计数暂时增加（我们期待后面有右括号来匹配它）。
2. 遇到 ')'：
   • 如果当前有未匹配的左括号（即左括号计数 > 0），说明这个右括号可以匹配掉一个左括号，那么我们将左括号计数减一。
   • 如果当前没有未匹配的左括号（即左括号计数 = 0），说明这个右括号是多余的，我们需要删除它，所以 rRemove 加一。
3. 遇到其他字符（字母）：跳过，不影响括号匹配。

遍历结束后，可能还存在未匹配的左括号（即左括号计数 > 0），这些就是多余的左括号，需要删除。所以 lRemove 的值就是最终剩余的左括号计数。

举例说明： 对于 s = "()())()"

• 初始化 lRemove = 0, rRemove = 0, 左括号计数 leftCount = 0
• 遍历：
  • '('：leftCount = 1
  • ')'：有左括号匹配，leftCount = 0
  • '('：leftCount = 1
  • ')'：有左括号匹配，leftCount = 0
  • ')'：无左括号匹配，rRemove = 1
  • '('：leftCount = 1
  • ')'：有左括号匹配，leftCount = 0
• 遍历结束，leftCount = 0，所以 lRemove = 0。
• 最终，lRemove = 0, rRemove = 1。这意味着我们最少需要删除 1 个右括号。

第三步：尝试所有可能的删除组合（回溯算法）

我们知道最少要删 lRemove 个左括号和 rRemove 个右括号。但具体删哪几个，我们需要尝试所有可能性，同时保证最终字符串是有效的。

我们可以使用回溯算法（深度优先搜索）来解决。

回溯算法的核心思想：

1. 我们从字符串的第一个字符开始处理。
2. 对于每个字符，我们有两种选择：
   • 保留这个字符。
   • 删除这个字符（只有当它是括号，并且我们还有对应的删除名额时）。
3. 我们递归地处理后续的字符，并更新剩余的删除名额。
4. 当处理完所有字符时，检查当前的字符串是否有效，并且我们已经用完了所有的删除名额（即 lRemove 和 rRemove 都为 0）。如果满足，这就是一个合法解。

但是，直接这样回溯会产生很多重复的结果。 例如，字符串 "())"，有两个连续的右括号。如果我们删除第一个右括号，得到 "()"；删除第二个右括号，也得到 "()"。结果是重复的。

第四步：避免重复结果与剪枝优化

为了避免重复，我们制定一个规则：如果连续的多个括号是相同的，我们只尝试删除第一个。这样可以避免因删除不同位置的相同括号而得到重复的结果。

回溯函数的参数设计：

• index：当前处理到的字符索引。
• lRemove：剩余需要删除的左括号数量。
• rRemove：剩余需要删除的右括号数量。
• leftCount：当前字符串中尚未被匹配的左括号数量（用于实时判断有效性）。
• path：当前已经构建的字符串。

剪枝优化：
在递归过程中，如果发现 leftCount < 0，说明当前路径中右括号多于左括号，已经无效，可以提前返回（剪枝）。
同样，如果 lRemove 或 rRemove 小于 0，说明删除得太多，也可以提前返回。

第五步：算法流程总结

1. 预处理： 遍历字符串，计算出初始的 lRemove 和 rRemove。
2. 回溯搜索：
   • 终止条件： 如果 index 等于字符串长度。
     • 如果 lRemove == 0 且 rRemove == 0 且 leftCount == 0，说明我们找到了一个有效解，将 path 加入结果集。
   • 选择一：尝试删除当前字符（如果是括号）
     • 如果当前字符是 '(' 且 lRemove > 0，或者当前字符是 ')' 且 rRemove > 0，我们可以选择删除它。
     • 去重判断： 如果当前字符和上一个字符相同，且上一个字符被跳过了（删除了），那么跳过当前字符（不删除）以避免重复。
     • 如果决定删除，则递归调用，更新 lRemove 或 rRemove，index+1，其他参数不变。
   • 选择二：保留当前字符
     • 更新 path。
     • 如果字符是 '('，leftCount + 1。
     • 如果字符是 ')'，先检查 leftCount 是否大于 0（保证有效性），然后 leftCount - 1。如果 leftCount 已经为 0，则不能保留这个右括号（剪枝）。
     • 递归调用，index+1。

第六步：代码实现（思路伪代码）

def removeInvalidParentheses(s):
    # 1. 计算需要删除的左右括号数
    lRemove, rRemove = 0, 0
    leftCount = 0
    for char in s:
        if char == '(':
            leftCount += 1
        elif char == ')':
            if leftCount == 0:
                rRemove += 1
            else:
                leftCount -= 1
    lRemove = leftCount # 最后剩余的未匹配左括号数

    res = []
    path = []

    def backtrack(index, lRemove, rRemove, leftCount):
        if index == len(s):
            # 检查是否满足条件
            if lRemove == 0 and rRemove == 0 and leftCount == 0:
                res.append(''.join(path))
            return

        char = s[index]
        # 尝试删除当前字符（如果是括号）
        if (char == '(' and lRemove > 0) or (char == ')' and rRemove > 0):
            # 去重：如果当前字符和上一个字符相同，且上一个字符没被保留（即被删了），则跳过本次删除
            if index > 0 and s[index] == s[index-1] and ... : # 详细判断条件略
                # 跳过
                pass
            else:
                # 选择删除
                new_lRemove = lRemove - 1 if char == '(' else lRemove
                new_rRemove = rRemove - 1 if char == ')' else rRemove
                backtrack(index + 1, new_lRemove, new_rRemove, leftCount)

        # 尝试保留当前字符
        path.append(char)
        if char == '(':
            backtrack(index + 1, lRemove, rRemove, leftCount + 1)
        elif char == ')':
            if leftCount > 0: # 有左括号可以匹配
                backtrack(index + 1, lRemove, rRemove, leftCount - 1)
            # else: 否则剪枝，保留这个右括号会导致无效
        else:
            # 是字母，直接保留
            backtrack(index + 1, lRemove, rRemove, leftCount)
        path.pop() # 回溯，撤销选择

    backtrack(0, lRemove, rRemove, 0)
    # 可能没有结果，返回空列表
    return res if res else [""]

最终输出： 这个算法会找到所有通过删除最少数量无效括号后形成的有效字符串。由于去重和剪枝，效率很高。