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

(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!