LeetCode 301：回溯算法优化删除无效括号

1. 题目背景与核心挑战

"删除无效的括号"是LeetCode上的一道经典回溯算法题目（编号301），要求从给定字符串中移除最少数量的无效括号，使剩余字符串成为有效的括号组合。这道题在亚马逊、Facebook等大厂面试中出现频率较高，因为它能全面考察候选人对以下知识点的掌握：

• 括号匹配的验证机制
• 回溯算法的剪枝优化
• 重复结果的处理技巧
• 时间复杂度的分析能力

典型输入输出示例：

code复制输入: "()())()"
输出: ["()()()", "(())()"]

2. 基础解法：暴力回溯实现

2.1 算法框架搭建

最直观的解法是使用回溯法枚举所有可能的删除方案。基础实现包含三个关键步骤：

python复制def removeInvalidParentheses(s):
    def is_valid(string):
        count = 0
        for char in string:
            if char == '(':
                count += 1
            elif char == ')':
                count -= 1
                if count < 0:
                    return False
        return count == 0

    def backtrack(index, path, open_count, remove_left, remove_right, results):
        # 实现回溯逻辑
        pass

    # 统计需要删除的左右括号数量
    left_remove, right_remove = 0, 0
    for char in s:
        if char == '(':
            left_remove += 1
        elif char == ')':
            if left_remove == 0:
                right_remove += 1
            else:
                left_remove -= 1

    result = set()
    backtrack(0, "", 0, left_remove, right_remove, result)
    return list(result)

2.2 关键参数说明

• open_count：记录当前路径中未匹配的左括号数
• remove_left/right：记录仍需删除的左右括号数
• results：使用集合自动去重

注意：直接使用列表收集结果会导致重复解，必须用集合去重

3. 回溯算法优化策略

3.1 剪枝条件设计

在基础回溯上添加四个关键剪枝条件：

1. 剩余字符不足剪枝：

python复制if len(s) - index < (remove_left + remove_right):
    return

2. 删除数量超额剪枝：

python复制if remove_left < 0 or remove_right < 0:
    return

3. 右括号超前剪枝：

python复制if char == ')' and open_count == 0:
    return

4. 连续相同字符剪枝：

python复制if index > 0 and char == s[index-1]:
    continue

3.2 完整优化实现

python复制def backtrack(index, path, open_count, remove_left, remove_right, results):
    if index == len(s):
        if open_count == 0 and remove_left == 0 and remove_right == 0:
            results.add(path)
        return
    
    char = s[index]
    
    # 剪枝条件1：剩余字符不足
    if len(s) - index < (remove_left + remove_right):
        return
        
    # 剪枝条件2：删除数量超额
    if remove_left < 0 or remove_right < 0:
        return
    
    # 非括号字符直接跳过
    if char not in '()':
        backtrack(index+1, path+char, open_count, remove_left, remove_right, results)
        return
    
    # 剪枝条件3：遇到右括号但无匹配左括号
    if char == ')' and open_count == 0:
        backtrack(index+1, path, open_count, remove_left, remove_right-1, results)
        return
    
    # 剪枝条件4：连续相同字符处理
    if index > 0 and char == s[index-1]:
        if char == '(':
            backtrack(index+1, path+char, open_count+1, remove_left, remove_right, results)
        else:
            backtrack(index+1, path+char, open_count-1, remove_left, remove_right, results)
        return
    
    # 选择删除当前字符
    if char == '(' and remove_left > 0:
        backtrack(index+1, path, open_count, remove_left-1, remove_right, results)
    elif char == ')' and remove_right > 0:
        backtrack(index+1, path, open_count, remove_left, remove_right-1, results)
    
    # 选择保留当前字符
    if char == '(':
        backtrack(index+1, path+char, open_count+1, remove_left, remove_right, results)
    else:
        backtrack(index+1, path+char, open_count-1, remove_left, remove_right, results)

4. 复杂度分析与测试用例

4.1 时间复杂度

• 最坏情况：O(2^n) （每个字符都有保留/删除两种选择）
• 优化后实际复杂度：O(k^m)
  • k：平均分支因子（约1.5-2.5）
  • m：需要删除的括号总数

4.2 空间复杂度

• 递归栈深度：O(n)
• 结果存储：O(m) （m为有效解的数量）

4.3 典型测试用例

python复制test_cases = [
    ("()())()", ["()()()", "(())()"]),
    ("(a)())()", ["(a)()()", "(a())()"]),
    (")(", [""]),
    ("n", ["n"]),
    ("((()((s((((()", ["()s()", "()(s)", "()s()"]),
    ("()()()()", ["()()()()"])
]

5. 常见错误与调试技巧

5.1 高频错误类型

1. 重复结果处理不当：

   • 错误做法：直接使用list.append()
   • 正确方案：使用set()自动去重

2. 剪枝条件遗漏：

   • 典型症状：运行超时（TLE）
   • 检查点：是否处理了连续相同字符的情况

3. 括号计数错误：

   • 调试方法：打印open_count的实时变化

5.2 调试日志示例

python复制def backtrack(...):
    print(f"index={index}, path={path}, open={open_count}, "
          f"del_l={remove_left}, del_r={remove_right}")
    # ...原有实现...

5.3 性能优化对比

6. 扩展思考与变种题目

6.1 算法变种

1. 返回任意一个有效结果：

   python复制def removeOneInvalid(s):
       # 找到第一个无效位置后立即返回修正结果
       pass
   

2. 统计所有删除方案数：

   python复制def countRemovals(s):
       # 动态规划统计方案数
       pass
   

6.2 相似题目推荐

• LeetCode 20：有效的括号（基础验证）
• LeetCode 22：括号生成（反向问题）
• LeetCode 32：最长有效括号（动态规划解法）
• LeetCode 678：有效的括号字符串（通配符处理）

在实际面试中，面试官可能会要求解释为什么选择回溯而非BFS（虽然BFS也能解但空间复杂度更高），或者如何进一步优化时间复杂度。我的经验是：当删除量超过5个时，可以考虑加入记忆化存储中间状态，但会显著增加空间复杂度