如何优化表达式中缺失算术运算符的查找效率？

1. 修复递归核心逻辑bug #

原代码中Recurse函数的for n in range(len(nums))循环末尾存在错误的return stack，导致循环仅执行一次，完全未遍历所有数字排列组合，这是导致计算效率低下且可能漏解的核心问题。必须移除该return语句，让循环完整遍历所有剩余数字的选择。

2. 提前剪枝，终止无效分支 #

在递归过程中实时判断当前分支是否可能得到目标值，直接终止无意义的递归：

• 除法操作：必须保证被除数能被除数整除，且结果为正整数，不符合则直接跳过该分支；
• 减法操作：必须保证结果为正整数，否则跳过；
• 计算当前表达式的最小/最大可能结果范围，如果目标值不在该范围内，直接终止当前分支。

3. 替换eval，实时计算结果 #

原代码依赖生成字符串后调用eval计算结果，效率极低。改为在递归过程中维护计算状态：

• 用current_sum记录加减运算的总和，current_term记录当前正在计算的乘除项数值，结合最后一个运算符的类型，实时更新计算结果，避免字符串拼接和eval的开销。

4. 记忆化缓存+去重 #

• 用lru_cache缓存已计算过的子问题：将剩余数字转换为可哈希的元组，结合当前计算状态作为缓存键，避免重复计算相同的子分支；
• 对重复数字去重：如果剩余数字中有多个相同数值（如两个3），选择第一个和第二个3的计算结果完全一致，直接跳过重复选择，减少冗余计算。

5. 优化运算符遍历顺序 #

根据目标值的大小调整运算符尝试顺序：

• 若目标值较大，优先尝试乘法，快速逼近目标；
• 若目标值较小，优先尝试加减，减少无效的大数计算分支。

优化后的核心代码示例 #

import sys
from functools import lru_cache

def solve(target, numbers):
    numbers = tuple(sorted(numbers))
    solution_count = 0
    final_expr = None

    def dfs(remaining_nums, current_sum, current_term, expr_path):
        nonlocal solution_count, final_expr
        if not remaining_nums:
            total = current_sum + current_term
            if total == target:
                solution_count += 1
                if solution_count > 1:
                    raise StopIteration
                final_expr = expr_path + str(current_term)
            return

        prev_num = None
        for i, num in enumerate(remaining_nums):
            if num == prev_num:
                continue
            prev_num = num
            new_remaining = remaining_nums[:i] + remaining_nums[i+1:]

            # 加法
            dfs(new_remaining, current_sum + current_term, num, f"{expr_path}{current_term}+")
            # 减法：结果必须为正
            if current_term - num > 0:
                dfs(new_remaining, current_sum, current_term - num, f"{expr_path}{current_term}-")
            # 乘法
            dfs(new_remaining, current_sum, current_term * num, f"{expr_path}{current_term}*")
            # 除法：整除且结果为正
            if current_term % num == 0 and (current_term // num) > 0:
                dfs(new_remaining, current_sum, current_term // num, f"{expr_path}{current_term}/")

    try:
        prev_num = None
        for i, num in enumerate(numbers):
            if num == prev_num:
                continue
            prev_num = num
            remaining = numbers[:i] + numbers[i+1:]
            dfs(remaining, 0, num, "")
    except StopIteration:
        return None, None

    if solution_count == 1:
        return final_expr, target
    else:
        return None, None

额外优化建议 #

• 谜题生成模块new_equation逻辑混乱，建议先生成合法的表达式（保证所有中间结果为正整数），再提取操作数和目标值，避免反复随机生成浪费时间；
• 针对15个操作数的场景，可使用多进程并行处理不同的数字排列分支，利用多核CPU资源进一步缩短计算时间。

内容的提问来源于stack exchange，提问作者Michael Schreiber