本文介绍一种比暴力组合更高效的子集积（subset product）判定方法——不依赖显式递归，而是通过逆向除法动态构建可达数集，自然剪枝超界分支，时间复杂度显著优于枚举所有组合。
本文介绍一种比暴力组合更高效的子集积（subset product）判定方法——不依赖显式递归，而是通过逆向除法动态构建可达数集，自然剪枝超界分支，时间复杂度显著优于枚举所有组合。
在正整数子集积问题中，给定目标值 $ N $ 和候选因子列表 $ S $，我们需要判断是否存在 $ S $ 的某个子集，其元素乘积恰好等于 $ N $。传统思路（如题中 itertools.combinations 枚举）虽直观，但存在严重冗余：一旦当前部分积已超过 $ N $，后续任何扩展均无效；而排序+限长（max_comb_size）仅粗略剪枝，无法在递归路径中动态感知“不可行性”。
值得指出的是，标准深度优先递归（DFS）本身并不会“自动知道”要剪枝——它必须由程序员显式设计剪枝逻辑（如当前积 > N 时立即回溯）。但题中提供的参考解法巧妙绕开了正向乘法搜索，转而采用逆向除法动态规划，从根本上规避了冗余：
def subset_product_exists(N, S):
# 预处理：仅保留能整除当前剩余目标的因子（且去重、去除非约数）
valid_S = [x for x in set(S) if x > 0 and N % x == 0]
if N == 1:
return 1 in S # 特殊情况：空积定义为1，但需至少一个1或直接命中
# P: 当前所有可通过S中因子逐步整除N得到的中间值（含N自身）
P = {N}
for s in valid_S:
# 对每个已知可达值 p，若 s 整除 p，则 p // s 也可达（对应选s作为因子）
new_vals = {p // s for p in P if p % s == 0}
P |= new_vals # 并入新可达值
return 1 in P
该算法核心思想是：若存在子集积为 $ N $，则必存在一条从 $ N $ 出发、每次被 $ S $ 中某元素整除的路径，最终抵达 $ 1 $。例如 $ N=320 $，$ S=[2,4,5] $，路径可为 $ 320 \xrightarrow{÷5} 64 \xrightarrow{÷4} 16 \xrightarrow{÷4} 4 \xrightarrow{÷4} 1 $，对应子集 $ {5,4,4,4} $。
关键优势在于天然剪枝：
- 每次只生成 $ p // s $（要求 $ s \mid p $），自动排除所有非整除情形；
- 所有中间值均 ≤ $ N $，且严格递减（因 $ s \geq 2 $ 时 $ p//s $ N $ 的无效状态；
- 使用集合 P 去重，避免重复计算同一中间值；
- 时间复杂度取决于可达状态数，通常远小于 $ \mathcal{O}(2^{|S|}) $。
注意事项：
- 必须预过滤 $ S $：移除非正数、非 $ N $ 约数（如题中 N % i == 0 判断），否则 p % s == 0 可能失效或引入无意义分支；
- 1 是特例：若 1 in S，则只要 1 in P 成立（即其他因子已凑出 $ N $）即可满足；无需额外处理，因 N // 1 == N 不新增状态，但存在性已由初始 P={N} 保证；
- 该方法判定存在性极快，但不直接返回具体子集；如需构造解，可辅以父指针记录或回溯映射。
综上，相比手动实现带剪枝的递归DFS，此逆向除法集合扩张法逻辑更简洁、剪枝更彻底、实现更鲁棒，是正整数子集积判定问题的推荐解法。
