欧拉计划118题：全数位素数集合计数DP算法错误排查

你的代码核心问题是递归过程中对同一有效集合进行了重复计数，导致结果远高于正确值（欧拉计划118题的正确答案是44680）。以下是具体原因和修复方案：

问题根源 #

原DP函数的递归逻辑是将集合拆分为任意两个非空子集，然后累加dp(a)*dp(b)。但dp(a)和dp(b)本身包含了多素数集合的情况，这会导致同一个最终集合被多次计数：

• 例如，集合{2,3,5}会被分别计为：先拆{2}和{3,5}，再拆{3,5}为{3}和{5}；以及先拆{5}和{2,3}，再拆{2,3}为{2}和{3}。两种拆分路径对应同一个集合，但被计数两次。

修复思路 #

通过固定起始元素避免重复计数：每次递归时，强制选择包含当前集合最小元素的素数作为第一个元素，然后递归处理剩余数字。这样每个有效集合只会被生成一次。

修正后的代码 #

from functools import cache
from collections import defaultdict
from pyprimesieve import primes

# 生成符合条件的素数：无重复数字、不含0、9位以内
primes_list = [
    p for p in primes(10**9) 
    if len(set(str(p))) == len(str(p)) and "0" not in str(p)
]

# 构建数字集合到对应素数数量的映射
set_counts = defaultdict(int)
for p in primes_list:
    digit_set = frozenset(map(int, str(p)))
    set_counts[digit_set] += 1

@cache
def dp(s):
    """
    计算给定数字集合对应的有效素数集合数量
    每个集合的素数数字不重叠，且覆盖所有给定数字
    """
    if not s:
        return 1  # 空集合的有效划分只有1种（自身）
    total = 0
    min_digit = min(s)
    other_digits = list(s - {min_digit})
    num_other = len(other_digits)
    
    # 遍历所有包含最小元素的子集（通过位掩码生成）
    for mask in range(1 << num_other):
        current_subset = {min_digit}
        for i in range(num_other):
            if mask & (1 << i):
                current_subset.add(other_digits[i])
        current_subset_frozen = frozenset(current_subset)
        # 累加当前子集对应的素数数量 × 剩余数字的有效集合数量
        total += set_counts[current_subset_frozen] * dp(s - current_subset_frozen)
    return total

# 计算1-9所有数字的有效集合数量
print(dp(frozenset(range(1, 10))))  # 输出44680

关键改进点 #

1. 固定起始元素：每次递归都从包含当前集合最小元素的子集开始，确保每个有效集合仅被计数一次。
2. 位掩码生成子集：高效遍历所有包含最小元素的子集，避免重复生成相同拆分。
3. 正确的基例：空集合返回1，对应“选择当前子集作为唯一素数”的情况。

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