How to make python halt once target product is found in subset?

Question

I've been learning python for my hobby and empirical research into NP-complete problems such as Subset Product. The algorithm I have works, but it's not doing it the way I intend to do.

What I'm trying to do is to stop itertools' combinations once it arrives to a subset product of the input variable target. This will slightly make the code faster. The code is in the polishing stage so there is an unnecessary list res_2

Here's the loop.

res_2 = [];
for i in range(1, len(s)+1):

   var = (findsubsets(s, i))   
   kk = list(map(numpy.prod, var))
   res_2.append(kk)
   if target in kk:
     print('yes')
     print(var)
     break

This is the output that I don't want. Notice that the script will not stop at the (4, 4). It's a waste of resources to continue checking all combinations once a target is "hit."

Enter numbers WITH SPACES: 4 4 3 12
enter target integer:
16
yes
[(4, 4), (4, 3), (4, 12), (4, 3), (4, 12), (3, 12)]
 kk
[16, 12, 48, 12, 48, 36]

My intended output is to stop at (4, 4) if its the first "hit." The same for any other subset like (1,2,3) or (1,2,3---any-length). I would prefer if the script continues until it's able to find a hit. Once it finds the hit, it stops, because this would improve the speed of the algorithm.

Full script below

# Naive Subset-Product solver
# with python's itertools

import itertools 
import numpy

s = list(map(int, input('Enter numbers WITH SPACES: ').split(' ')))
print('enter target integer: ')
target = int(input())


if s.count(target) > 0:
   print('yes')
   quit()

if target > numpy.prod(s):
  print('sorry cant be bigger than total product of s')
  quit()


def findsubsets(s, n): 
    return list(itertools.combinations(s, n)) 

# Driver Code 
n = len(s)

# This code snippet is a for loop. It also is intended to cut down execution
# time once it finds the target integer. (instead of creating all combinations)

res_2 = [];
for i in range(1, len(s)+1):

   var = (findsubsets(s, i))   
   kk = list(map(numpy.prod, var))
   res_2.append(kk)
   if target in kk:
     print('yes')
     print(var)
     break

Question

How do I get this to work to increase the speed of the algorithm? What pythonic tricks would fix my problem? Is there a shorter way of doing this?

Trafalgar

Answer 1

It's premature to convert the itertools' combinations return value into a list, especially when you're trying to exit early and avoid too much overhead. There's usually a good reason that library functions return iterators rather than fully-realized lists.

Here's a suggestion:

def findsubsets(s, n): 
    return itertools.combinations(s, n)

def find_subset(target,nums):
    for i in range(1,len(nums)+1):
        for ss in findsubsets(nums, i):
            if np.prod(ss) == target:
                prodstr = '*'.join(str(num) for num in ss)
                print(f"{target} = {prodstr}")
                return ss
    return None

find_subset(96,[1,6,2,8])

Given that findsubsets is a single line, it's kind of questionable to have it as a standalone function (we're basically just aliasing combinations which could have been done with an import X as Y statement). In any case, this should stop early without hogging too much RAM with larger inputs.

Paste