Subset Product This next one asks you to employ a common recursive pattern - tha
ID: 3708274 • Letter: S
Question
Subset Product This next one asks you to employ a common recursive pattern - that of computing all the subsets of a given set of things. In this problem, you are to determine whether or not an integer P > 1 can be computed as the product of any combination of a provided list of integers (where each factor f> 0 can only be used once) Examples: given P10, and the list [2, 3, 4, 5], we see that 2 x 5-10, so the answer is yes given P81, and the list [2, 2, 3, 3,4,9),3x3x9- 81, so the answer is yes given P = 100 and the list [3, 4, 5, 8, 101, the answer is no Complete the implementation of the recursive can_make_product, which returns True or False based on whether the argument p can be computed as the product of some subset of the list of integers vals def can_make_product(p, vals): # YOUR CODE HERE raise NotImplementedError ()Explanation / Answer
PROGRAM:
AS PER THE GIVEN DATA WE CAN WRITTEN AS
SHOWN BELOW
def can_make_product(product, array):
count = len(array) # this gets the length of the array
#print(array) # you can add this to debug
if count == 2: # if only 2 elements in the array
if array[0] * array[1] == product: # and they both multiply to the product
return True
return False # but if they don't..
i = 0
while i < count:
if product % array[i] == 0:
if product == array[i] or True == can_make_product(product/array[i], array[0:i] + array[i+1:count]):
return True # if the number is equal to the product or if the array has the product
i = i + 1 # inc. i
return False # so it probably is not present..
Rest is driver code:
from unittest import TestCase
tc = TestCase()
tc.assertTrue(can_make_product(10, [2, 5]))
tc.assertTrue(can_make_product(10, [2, 3, 4, 5]))
tc.assertTrue(can_make_product(10, [3, 4, 2, 5]))
tc.assertTrue(can_make_product(10, [10]))
tc.assertTrue(can_make_product(81, [2, 2, 3, 3, 4, 9]))
tc.assertTrue(can_make_product(66402, [2, 4, 5, 12, 17, 25, 31, 63]))
tc.assertFalse(can_make_product(10, [2, 2, 2, 4]))
tc.assertFalse(can_make_product(243, [2, 2, 3, 3, 3, 4, 4, 4]))
tc.assertFalse(can_make_product(81, [2, 3, 5, 9, 11]))
tc.assertFalse(can_make_product(100, [3, 4, 5, 8, 10]))
tc.assertFalse(can_make_product(12369, [3, 4, 5, 8, 19, 20, 31]))