在Python中遞歸的子集總和

Question

我很樂意爲您提供幫助。

我有以下問題：

我提供的數字seq列表和目標號碼，我需要寫兩件事情：

1. 遞歸解決方案，返回True如果有是等於目標號碼的子序列的總和，否則爲False。 例如：

   subset_sum([-1,1,5,4],0) # True 
   subset_sum([-1,1,5,4],-3) # False 
   

2. 其次，我需要編寫使用的是什麼我在以前的解決方案 寫了一個解決方案，但現在的memoization使用字典中的鍵的元組： (len(seq),target)

對於1號這是我迄今：

def subset_sum(seq, target): 
    if target == 0: 
     return True 
    if seq[0] == target: 
     return True 
    if len(seq) > 1: 
     return subset_sum(seq[1:],target-seq[0]) or subset_sum(seq[1:],target) 
    return False 

不知道我如果我能得到一些意見，我會很感激。

對於2號：

def subset_sum_mem(seq, target, mem=None): 
    if not mem: 
     mem = {} 
    key=(len(seq),target) 
    if key not in mem: 
     if target == 0 or seq[0]==target: 
      mem[key] = True 
     if len(seq)>1: 
      mem[key] = subset_sum_mem(seq[1:],target-seq[0],mem) or subset_sum_mem(seq[1:],target,mem) 
     mem[key] = False 

    return mem[key] 

我不能讓記憶化給我正確的答案，所以我會很高興在這裏的一些指導。

感謝任何人願意幫忙！

Answer 1

我有這樣的修改後的代碼：

def subset_sum(seq, target): 
    left, right = seq[0], seq[1:] 
    return target in (0, left) or \ 
     (bool(right) and (subset_sum(right, target - left) or subset_sum(right, target))) 

def subset_sum_mem(seq, target, mem=None): 
    mem = mem or {} 
    key = (len(seq), target) 
    if key not in mem: 
     left, right = seq[0], seq[1:] 
     mem[key] = target in (0, left) or \ 
      (bool(right) and (subset_sum_mem(right, target - left, mem) or subset_sum_mem(right, target, mem))) 
    return mem[key] 

你能否提供一些測試情況下，這不工作？

Answer 2

這是我會寫的subset_sum：

def subset_sum(seq, target): 
    if target == 0: 
     return True 

    for i in range(len(seq)): 
     if subset_sum(seq[:i] + seq[i+1:], target - seq[i]): 
      return True 
    return False 

它的工作的一對夫婦的例子：

>>> subset_sum([-1,1,5,4], 0)) 
True 
>>> subset_sum([-1,1,5,4], 10) 
True 
>>> subset_sum([-1,1,5,4], 4) 
True 
>>> subset_sum([-1,1,5,4], -3) 
False 
>>> subset_sum([-1,1,5,4], -4) 
False 

說實話，我不知道如何memoize的它。

舊編輯：我用any()刪除了解決方案，因爲經過一些測試後我發現速度會變慢！

更新：只是出於好奇，你也可以使用itertools.combinations：

from itertools import combinations 

def com_subset_sum(seq, target): 
    if target == 0 or target in seq: 
     return True 

    for r in range(2, len(seq)): 
     for subset in combinations(seq, r): 
      if sum(subset) == target: 
       return True 
    return False 

這可以做的更好，在某些情況下，但在另將掛起（這是無論如何更好，然後遞歸的動態規劃方法方法）。

Answer 3

僅供參考，下面是一個使用動態規劃的解決方案：

def positive_negative_sums(seq): 
    P, N = 0, 0 
    for e in seq: 
     if e >= 0: 
      P += e 
     else: 
      N += e 
    return P, N 

def subset_sum(seq, s=0): 
    P, N = positive_negative_sums(seq) 
    if not seq or s < N or s > P: 
     return False 
    n, m = len(seq), P - N + 1 
    table = [[False] * m for x in xrange(n)] 
    table[0][seq[0]] = True 
    for i in xrange(1, n): 
     for j in xrange(N, P+1): 
      table[i][j] = seq[i] == j or table[i-1][j] or table[i-1][j-seq[i]] 
    return table[n-1][s]