Проверка целевого продукта в виде списка (рекурсия)

Question

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 является продуктом, который я ищу в списке vals. Однако приведенный выше код работает только для кратных двух чисел за раз, а не для всех возможных подмножеств. Есть ли более простой способ использования рекурсии? Например, данный p=81, а также список [2, 2, 3, 3, 4, 9], 3×3×9=81, он должен вернуть true.

Answer 1

Это должно работать:

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)