Adi_S Adi_S - 14 days ago 6
Python Question

Checking for a target product within a list(recursion)

def can_make_product(p, vals):
if len(vals)==1:
if p==vals[0]:
return True
else:
return False

for i in range(len(vals)):
for k in range(i,len(vals)):

if vals[i] * vals[k]==p:
return True

return False


p
is the product that I'm looking for in the list
vals
. However, the above code only works for multiples of 2 numbers at a time and not for all possible subsets. Is there a much easier way using recursion?
For example, given
p=81
, and the list
[2, 2, 3, 3, 4, 9]
,
3×3×9=81
, it should return
true
.

Answer

This should work:

def can_make_product(p, vals):
    # base case empty list: n**0 == 1 for all n
    try:
        head, tail = vals[0], vals[1:]
    except IndexError:
        return p == 1
    # recursive step: try tail of vals with/without head
    if not p % head and can_make_product(p//head, tail):
        return True
    return can_make_product(p, tail)
Comments