时间戳

首页 > 解决方案 > 查找具有预定义总和的子序列

python - 查找具有预定义总和的子序列

问题描述

嘿stackoverflow社区，

我有以下问题。我有预定义的数字列表。例如

input_list = [2, 2, 2, 2, 2, 1, 1, -6, -6, -4, 3, 3, -8]

我不想尝试完成的是找到一个具有给定结果列表大小和结果列表总和的子集，以便每个结果列表都具有请求的大小和请求的总和。

例如：

>> get_all_sum_lists(input_list, size=3, sum=0)
[[2, 2, -4], [-6, 3, 3], ...]
>> get_all_sum_lists(input_list, size=2, sum=-1)
[[3, -4]]
>> get_all_sum_lists(input_list, size=1, sum=0)
[]

第一个想法：直接的解决方案是尝试每种组合，但这很糟糕。这最终会在 O(n^size) 第二个想法：这个问题有一些有趣的属性，如：

get_all_sum_lists(input_list, size=4, sum=3) in get_all_sum_lists(input_list, size=2, sum=1).extend(get_all_sum_lists(input_list, size=2, sum=2))

所以我认为递归或归纳之类的东西可以工作。但是我构建从 size=1 到请求大小的所有内容的想法导致与上述 O(n^size) 相同的复杂性

有人有一个复杂度较低的解决方案吗？

标签： pythonarrayslistrecursion

解决方案

使用 itertools 组合，您可以获得所需长度的子列表，然后您可以按总和过滤它们。不过我不确定性能，让我知道它是否体面：

import itertools

def f(list_, length_, sum_):
    return list(set([i for i in itertools.combinations(list_, length_) if sum(i)==sum_]))

您的 input_list 示例：

f(input_list, 3, 0)

[(-6, 3, 3), (2, 2, -4), (1, -4, 3)]

f(input_list, 5, 10)

[(2, 2, 2, 1, 3), (2, 2, 2, 2, 2), (2, 1, 1, 3, 3)]

推荐阅读