如果我使用递归来解决子集乘积，它会“知道”不要使用乘积 > N 的组合来避免冗余吗？

Question

我正在求解正整数的子集积，我得到了一个除数列表 S 和一个整数 N。 我必须决定是否存在等于目标的组合。

我将从 S 中删除非约数，删除 1 的重复项，因为任何组合都等于 1，这不会影响正确性。我从最小到最大排序，因为这是我的代码按预期工作的要求。

我通过迭代并乘以 S 中的整数来找到最大组合大小，直到我们 <= N。然后我将组合限制为该大小。

我处理可以有效解决的特殊情况。

• 如果 S 中所有元素的乘积等于 N，则返回 True。
• 如果 S 中所有元素的乘积小于 N，则返回 False。

代码然后执行所有组合，直到 max_comb_size 并输出 True 或 False。

我想使用更有效的方法来避免更多冗余组合，但我需要确保递归确实有效并且“知道”有一个max_comb_size。对于这个变体子集产品，递归方法会是什么样子？

第一部分

from itertools import combinations
from itertools import product
import sys
from collections import deque

def check_divisors(N, S):
    # Multiset Subset Product General Case for positive integers only
    # Initialize the maximum combination size
    max_comb_size = 0

    # Calculate the product of divisors and find the maximum combination size
    # without exceeding N
    # The variable max_comb_size effectively bounds the size of combinations
    divisor_product = 1
    for divisor in S:
        if divisor_product * divisor <= N:
            max_comb_size += 1
            divisor_product *= divisor
        else:
            break
    # Case where all elements of S have a total product equal to N
    product = 1
    for num in S:
        product *= num
    if product == N:
        return True
    # Case where all elements of S have a product less than N
    if product < N:
        return False
    # Try combinations of divisors starting from the smallest ones
    for comb_size in range(1, max_comb_size + 1):
        for combo in combinations(S, comb_size):
            # Calculate the product of the current combination
            current_product = 1  # Renamed the variable to avoid shadowing
            for divisor in combo:
                current_product *= divisor
            
            # If the product equals N, return True
            if current_product == N:
                return True
    
    # If no combination has a product equal to N, return False
    return False

第二部分

N = 320
S = [1,1,1,2,2,4,4,4,4,5,6]
# Remove non_divisors so that max_combo_size doesn't get confused.
# Also, 1's should only appear once, otherwise max_combo_size
# gets confused.
new_S = deque([])
flag = 0
for i in S:
    if i != 1:
        if N % i == 0:
            new_S.append(i)
    if i == 1:
        flag = 1
# O(1) insertion, only one 1 is allowed
# as it confuses max_combination_size. Doesn't
# affect correctness as any combination of 1 has
# a product of 1*n
if flag == 1:
    new_S.appendleft(1)
# Sorting is required for max_comb_size to work.
S = sorted(new_S)
print(check_divisors(N, S))

Answer 1

在您当前的方法中，您正在检查每种可能的组合以找到解决方案，从而导致复杂性为 O(2^len(elements))。虽然您的概念是正确的，但实际执行比需要的要复杂。

将您的方法视为浏览决策树。在每一点上，您都在做出选择：要么将当前乘积乘以列表中的新元素，要么跳过它并继续。此过程类似于对所有可能的组合进行深度优先搜索。这可以通过递归调用来实现，该递归调用调用同一函数两次：一次包含元素，一次排除它。

停止进一步不必要的探索：如果产品在任何时候超出了你的目标，你就立即停止探索之路。这显着减少了您需要检查的路径数量，因为产品可能很快变得非常大，从而提前达到此停止条件。

在此方法中排序不是必需的，但删除重复的是必要的。

  def is_product_possible(elements, target, current_product=1):
        if current_product == target:
            return True
        if current_product > target or len(elements) == 0:
            return False
        last_element = elements[-1]
        new_elements = elements[:-1]
        return is_product_possible(new_elements, target, current_product) or is_product_possible(new_elements, target, current_product * last_element)