計算如果給定列表的子集的總和遞歸

Question

存在

我需要建立接收的整數列表（數字）和一個非負整數（目標）的遞歸函數。

功能將查找給定列表中的任何可能的子集，如果它的值相加後等於目標，返回True。

def subset_sum(numbers, target): 
    ''' 
    numbers - a list of positive integers 
    target - a non-negative integer 
    returns True if the list 'numbers' has a sub-list with sum 'target', 
      False otherwise. 
    ''' 

Side Note: [] is a subset of any given list (set) 

例子：

subset_sum([1,2,3,4], 8): 

True 

subset_sum([1,2,3,4], 11): 

False 

subset_sum([4,4,4], 05): 

True 

subset_sum([4,4,4], 11): 

False 

subset_sum([], 0): 

True 

任何幫助表示讚賞！

Answer 1

這是關於子集和問題的一個變種（子問題），你可以讀到這裏：

https://en.wikipedia.org/wiki/Subset_sum_problem

有提出了一個僞算法，大約解決了這個問題在多項式時間內對任何整數（正數或負數）。有趣的是，這張貼在Stackoverflow和python上！

Fast solution to Subset sum