If I used recursion to solve Subset Product, would it "know" not to use combinations with a product > N to avoid redundancy?

Question

I'm solving Subset Product for positive integers, I'm given a list S of divisors and an integer N. I must decide if a combination exists that equals to target.

I will remove non-divisors from S, remove duplicates of 1 as any combination equals 1 and this does not affect the correctness. I sort from smallest to largest as that's a requirement for my code to work as intended.

I find the max combination size by iterating and multiplying through the integers in S until we <= N. I then cap the combinations to that size.

I handle special cases that are efficiently solvable.

• If the product of all elements in S equals N, return True.
• If the product of all elements in S is less than N, return False.

The code then does all combinations up to max_comb_size and either outputs True or False.

I would like to use a more efficient method to avoid even more redundant combinations, but I need to make sure recursion is actually working and "knows" that there's a max_comb_size. What would a recursive method look like for this variant Subset Product?

Part One

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

Part Two

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

In your current approach, you're examining every possible combination to find the solution, leading to a complexity of O(2^len(elements)). While your concept is on point, the actual execution is more complicated than it needs to be.

Think of your approach as navigating through a decision tree. At each point, you're making a choice: either you multiply the current product by a new element from your list, or you skip it and move on. This process is similar to conducting a depth-first search through all the possible combinations. This could be implemented through a recursive call that invokes the same function twice: once including the element and once excluding it.

To halt further unecessary explorations: if at any point the product exceeds your target, you immediately stop that path of exploration. This significantly cuts down the number of paths you need to examine because products can quickly become very large, hitting this stop condition early.

Sorting is not necessary in this approach however removing duplicated ones is.

  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

(Note: I'm aware this isn't recursive. I don't see a similarly efficient and simple recursive one, although Stef's seems comparable (either one might have advantages).)

Building the set of all numbers reachable from N by divisions, and reporting whether 1 got reached:

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)

Attempt This Online!

Answer 3

Iterate over the indices i of S and for each element S[i], make a recursive call that tries dividing N by S[i] and a recursive call that tries not dividing N by S[i]:

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))
        )