在Python中递归求和子集 [英] Subset sum recursively in Python

问题描述

我很乐意得到帮助。

我有以下问题：

我m给定了数字 seq 的列表和目标数字，我需要写两件事：

I'm given a list of numbers seq and a target number and I need to write 2 things:

1. 一个递归解决方案，如果子序列的总和等于目标数且 False True c $ c>否则。
   示例：

1. A recursive solution that returns True if there is a sum of a subsequence that equals the target number and False otherwise. example:

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

其次，我需要使用上一个解决方案
中编写的内容编写一个解决方案，但是现在要使用带有字典的记忆，该字典中的键是元组：
（len（seq ），target）

对于数字1，这是我到目前为止所要做的：

For number 1 this is what I got to so far:

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

不确定我是否正确，因此，如果我能得到一些建议，我将不胜感激。

Not sure I got it right so if I could get some input I will be grateful.

对于数字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]

我无法获得要给我正确答案的备忘，因此我很高兴在这里提供一些指导。

I can't get the memoization to give me the correct answer so I'd be glad for some guidance here.

感谢任何愿意提供帮助的人！

Thanks for anyone willing to help!

推荐答案

仅供参考，以下是使用动态编程的解决方案：

Just for reference, here's a solution using dynamic programming:

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]

这篇关于在Python中递归求和子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！