在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]