如何实现支持最大组合数限制的递归式Subset Product求解方法？

问题背景 #

我正在解决正整数的子集乘积问题：给定除数列表S和整数N，判断是否存在S的子集组合，其乘积等于目标值N。

预处理步骤 #

我会先对S做以下预处理：

• 移除非N的除数
• 去除重复的1（因为1的任意组合乘积都是1，不影响结果正确性）
• 将S从小到大排序（这是后续逻辑正常运行的必要条件）

现有思路与优化需求 #

我通过遍历S并累乘元素，直到乘积超过N，以此确定最大组合数max_comb_size，把组合规模限制在这个范围内。同时处理两类特殊情况：

• 若S所有元素的乘积等于N，直接返回True；
• 若S所有元素的乘积小于N，直接返回False。

当前代码通过遍历所有规模不超过max_comb_size的组合来判断结果，但效率较低，希望改用更高效的递归方法减少冗余计算，且递归逻辑要能识别max_comb_size的限制。

现有代码实现 #

Part One：组合遍历版核心函数 #

from itertools import combinations
import sys
from collections import deque

def check_divisors(N, S):
    # 仅针对正整数的多重集子集乘积通用情况
    max_comb_size = 0

    # 计算不超过N的最大组合规模
    divisor_product = 1
    for divisor in S:
        if divisor_product * divisor <= N:
            max_comb_size += 1
            divisor_product *= divisor
        else:
            break
    
    # 特殊情况1：所有元素乘积等于N
    total_product = 1
    for num in S:
        total_product *= num
    if total_product == N:
        return True
    
    # 特殊情况2：所有元素乘积小于N
    if total_product < N:
        return False
    
    # 遍历所有符合规模限制的组合
    for comb_size in range(1, max_comb_size + 1):
        for combo in combinations(S, comb_size):
            current_product = 1
            for divisor in combo:
                current_product *= divisor
            if current_product == N:
                return True
    
    return False

Part Two：预处理与测试代码 #

N = 320
S = [1,1,1,2,2,4,4,4,4,5,6]
# 移除非除数，且仅保留一个1（避免干扰max_comb_size计算）
new_S = deque([])
has_one = 0
for i in S:
    if i != 1:
        if N % i == 0:
            new_S.append(i)
    else:
        has_one = 1
# 最多保留一个1，不影响正确性（1的任意组合乘积都是1*n）
if has_one == 1:
    new_S.appendleft(1)
# 排序是max_comb_size计算的必要条件
S = sorted(new_S)
print(check_divisors(N, S))

递归实现方案 #

递归的核心思路是回溯剪枝：从第一个元素开始，选择包含或不包含当前元素，同时跟踪当前乘积和已选元素的数量，一旦超过max_comb_size或者乘积超过N就直接剪枝，避免无效计算。

递归核心函数实现 #

def recursive_check(N, S, max_comb_size):
    # 递归辅助函数，参数：当前索引、当前乘积、已选元素数量
    def backtrack(index, current_product, count):
        # 终止条件：乘积等于N，返回True
        if current_product == N:
            return True
        # 剪枝条件：索引越界、已选数量超过max_comb_size、乘积超过N
        if index >= len(S) or count >= max_comb_size or current_product > N:
            return False
        
        # 选择当前元素：如果当前元素乘进去不超过N，则继续递归
        if current_product * S[index] <= N:
            if backtrack(index + 1, current_product * S[index], count + 1):
                return True
        
        # 不选择当前元素：直接跳过，递归下一个元素
        if backtrack(index + 1, current_product, count):
            return True
        
        # 两种选择都没找到，返回False
        return False
    
    # 从索引0开始，初始乘积1，已选数量0
    return backtrack(0, 1, 0)

整合后的完整函数 #

把递归逻辑整合到原有的check_divisors函数中，替换掉组合遍历的部分：

from collections import deque

def check_divisors_recursive(N, S):
    max_comb_size = 0
    divisor_product = 1
    for divisor in S:
        if divisor_product * divisor <= N:
            max_comb_size += 1
            divisor_product *= divisor
        else:
            break
    
    # 处理特殊情况
    total_product = 1
    for num in S:
        total_product *= num
    if total_product == N:
        return True
    if total_product < N:
        return False
    
    # 调用递归回溯函数
    return recursive_check(N, S, max_comb_size)

测试代码（复用原预处理逻辑） #

N = 320
S = [1,1,1,2,2,4,4,4,4,5,6]
new_S = deque([])
has_one = 0
for i in S:
    if i != 1:
        if N % i == 0:
            new_S.append(i)
    else:
        has_one = 1
if has_one == 1:
    new_S.appendleft(1)
S = sorted(new_S)
print(check_divisors_recursive(N, S))  # 输出True，因为2*4*4*5=320

递归实现的优势 #

1. 剪枝优化：一旦当前乘积超过N或者已选元素数量达到max_comb_size，就停止该分支的递归，避免大量无效计算；
2. 提前终止：只要找到符合条件的子集就立即返回结果，无需遍历所有可能；
3. 空间效率：递归的空间复杂度主要由调用栈决定，远低于组合遍历中生成所有组合的空间开销。

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