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]

您能提供一些这不起作用的测试用例吗？