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

Question

我正在解决一个关于正整数的子集乘积问题。我有一个包含除数的列表S和一个整数N。我的任务是判断是否存在某种组合，使得它们的乘积等于目标值。

首先，我会从S中去掉那些不是除数的数字，并且去掉重复的1，因为任何组合中有1都不会影响结果的正确性。接着，我会把剩下的数字从小到大排序，因为这是我代码正常运行的一个要求。

然后，我通过遍历S中的数字并进行相乘，找到最大的组合大小，直到乘积小于等于N。之后，我会把组合限制在这个大小之内。

我会处理一些特殊情况，这些情况可以高效解决。

• 如果S中所有元素的乘积等于N，那么返回真（True）。
• 如果S中所有元素的乘积小于N，那么返回假（False）。

接下来，代码会生成所有最多到max_comb_size的组合，并输出真或假。

我希望能用一种更高效的方法来避免更多冗余的组合，但我需要确保递归方法能正常工作，并且“知道”有一个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)

Answer 2

遍历字符串 S 中的每个位置 i，对于每个元素 S[i]，我们要进行两次递归调用：一次是尝试用 S[i] 去除 N，另一次是尝试不去除 N。

from functools import cache

@cache
def f(n, i=0):
    if i == len(S):
        return (n == 1)
    else:
        return (
            f(n, i+1) or
            (n % S[i] == 0 and f(n // S[i], i+1))
        )

Answer 3

（注意：我知道这不是递归的。我没有找到一个同样高效且简单的递归版本，虽然Stef的看起来也不错（两者可能各有优缺点）。）

这个方法是通过不断地进行除法运算，来找出从数字N出发能得到的所有数字，并检查是否能得到1：

N = 320
S = [1,1,1,2,2,4,4,4,4,5,6]

P = {N}
for s in S:
    P |= {p // s
          for p in P
          if not p % s}

print(1 in P)

在线尝试这个！