檢查目標產品列表中（遞歸）

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要找的產品。但是，上述代碼一次只適用於2個數字的倍數，並不適用於所有可能的子集。使用遞歸有更簡單的方法嗎？例如，給定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)