Adi_S Adi_S - 1 year ago 95
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
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

is the product that I'm looking for in the list
. 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
, and the list
[2, 2, 3, 3, 4, 9]
, it should return

Answer Source

This should work:

def can_make_product(p, vals):
    # base case empty list: n**0 == 1 for all n
        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)
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download