python中无限数字流的目标总和

Question

我试图找到一个目标总和可以从 Python 中的无限数字流中找到。数字是正数（数字> 0），唯一且数字不确定。我相信答案是使用动态编程或堆，但不能完全弄清楚逻辑。关于可能的数据结构或逻辑流程的任何帮助都可以尝试。太感谢了。例如    nums = [ 99,85,1,3,6,72,7,9,22,....]    targetSum = 27output: TrueExplanation: 1+6+22 = 27(targetSum)

Answer 1

您可以使用一个集合来跟踪到目前为止在迭代中给出的数字的所有可能总和。对于每次迭代，将当前数字添加到集合中的每个现有总和以添加到集合中，并将当前数字本身添加到集合中。True当目标和确实在集合中时返回：

def has_sum(nums, targetSum):

    sums = set()

    for i in nums:

        sums.update([s + i for s in sums if s + i <= targetSum])

        if i <= targetSum:

            sums.add(i)

        if targetSum in sums:

            return True

    return False

以便：

has_sum([99, 85, 1, 3, 6, 72, 7, 9, 22], 29)

返回True（因为 1 + 6 + 22 = 29），并且：

has_sum([99, 85, 1, 3, 6, 72, 7, 9, 22], 27)

返回False（因为您问题中的预期输出不正确）。

Answer 2

您可以递归地尝试满足给定序列中有或没有第一个数字的目标总和，直到给定序列中没有更多数字，或者直到给定目标总和不再为正（因为您在评论中提到所有给定的数字是正数）：

def has_sum(nums, targetSum):

    if not nums or targetSum <= 0:

        return False

    first, *rest = nums

    return first == targetSum or has_sum(rest, targetSum - first) or has_sum(rest, targetSum)

以便：

has_sum([99, 85, 1, 3, 6, 72, 7, 9, 22], 29)

返回True（因为 1 + 6 + 22 = 29），并且：

has_sum([99, 85, 1, 3, 6, 72, 7, 9, 22], 27)

返回False（因为您问题中的预期输出不正确）。

编辑：为了避免在每次调用中将输入序列减去第一项复制到性能影响rest，可以使用索引改进上面的代码：

def has_sum(nums, targetSum, index=0):

    if index == len(nums) or targetSum <= 0:

        return False

    num = nums[index]

    return num == targetSum or has_sum(nums, targetSum - num, index + 1) or has_sum(nums, targetSum, index + 1)

Answer 3

我能想到的一个想法是使用紧密图。您可以执行以下操作：

1. 将小于总和的每个数字元素作为节点添加到图中

2. 每个新节点都连接到图中已经存在的每个其他节点

3. 添加到图形后，使用广度优先搜索从最低元素计算总和

我认为这个过程很慢