Edit: Recommended for Desktop Reddit not mobile.

This variant of Subset Product remains NP-complete as Exact-3-cover can reduce into it using primes for the Universe S and the collection of valid 3-lists treated as arbitrary combinations. Since, the product of S is a unique factorization no other combination could lead to false results when using a Subset Product algorithm for Exact-3-Cover.

The rules of combinations means no permutations of the same 3-list so they're unique. This does not affect the correctness of solving Exact-3-cover. This is easily filtered in an input_validation function.

Edit: I think people confuse subset sum dynamic solution could be used for subset product. The problem structure does not seem to allow this. So I'm looking for something else, and I think I found it.

This variant of Subset Product requires no duplicates and whole number divisors only.

Here we import the math module and assign the variables.

import math
max_subset_size = 0
N = 10

Initiate the while loop until N reaches 10,000

while N < 10000:

Generate the divisors of N and sort in ascending order (this is required for my algorithm to find the max_subset_size)

S = [i for i in range(1, N   1)]
S = sorted([num for num in set(S) if N % num == 0])

Iterate through the divisors, keep track of the product of the divisors and increments by 1 until product exceeds or equals N. The reason, we do this is because we know any subset larger than this cannot possibly have a solution. Correctness is not affected.

    max_subset_size = 0
    divisor_product = 1
    for divisor in S:
        if divisor_product * divisor <= N:
            max_subset_size  = 1
            divisor_product *= divisor
        else:
            break

Calculate the total combinations from 1 to max_subset_size (abridged for post readability)

    # We will use math to find all combinations from 1 to max_subset_size
    total_combinations = 0
    for k in range(1, max_subset_size   1):
        total_combinations  = math.comb(len(S), k)
    print('---------------------------------------------------------')
    print("N :", N, "total combinations :", total_combinations)
    print('---------------------------------------------------------')
    print("N^log(N) > ... :", N**int(math.log(N)) > total_combinations)
    if N**int(math.log(N)) < total_combinations:
        print('NOT N^log(N) time complexity')
        break

RESULTS

N : 9999 total combinations : 1585
Nlog(N) > total_combinations : True
N : 10000 total combinations : 245505
Nlog(N) > total_combinations : True