 # Solving Subset Product

a guest
Apr 23rd, 2022
270
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import itertools
2. from itertools import combinations
3. from functools import reduce
4. from operator import mul
5. from sys import exit
6. # Given a whole number > 0 for TARGET, and a set of whole numbers > 0 that are divisors of TARGET. Is there a combination of divisors in SET that have a total product equivalent to TARGET?
7. TARGET = int(input('enter target product: ' ))
8. SET = input('Enter numbers: ').split(',')
9. SET = list(set([int(a) for a in SET]))
10. # Using two-sum solution for two-product
11. two_prod_dict = {}
12. for a in range(0, len(SET)):
13.     if TARGET//int(SET[a]) in two_prod_dict:
14.         print('YES')
15.         exit(0)
16.     else:
17.        two_prod_dict[int(SET[a])] = a
18. # creating a set of all whole number divisors
19. divisors = set()
20. for i in SET:
21.     if TARGET % i == 0:
23. # Divisors are sorted in ascending order.
24. # so that max_combo can correctly select
25. # the largest possible combination size.
26. divisors = sorted(divisors)
27. if TARGET in divisors:
28.     print('YES')
29.     exit(0)
30. # finds the maximum combination size
31. # Simply multiplies each I in divisors
32. # until reaches the closest
33. # value without going over.
34. # A combination's total product cannot be larger
35. # than the TARGET.
36. max_combo = []
37. for a in divisors:
38.     max_combo.append(a)
39.     if reduce(mul,max_combo) >= TARGET:
40.         if reduce(mul,max_combo) > TARGET:
41.             max_combo.pop()
42.             break
43.         else:
44.             break
45. # Using any other divisor will go over TARGET.
46. # To save running time, do it only one time.
47. for X in combinations(divisors, len(max_combo)):
48.     if reduce(mul, X) == TARGET:
49.         print('YES')
50.         exit(0)
51.     else:
52.         break
53. # I'm hoping that smaller solutions
54. # are more likely than larger solutions so start
55. # with the smallest and work your way up.
56. for A in range(3, len(max_combo) + 1):
57.     for X in combinations(divisors, A):
58.         if reduce(mul, X) == TARGET:
59.             print('YES',X)
60.             exit(0)
61. print('NO')