查找总和为特定数字的数字列表的算法

Question

我正在学习python但我遇到了这个任务

我有一个数字列表 0<=n<=(end)，我想找到具有 6 个元素的列表的所有组合，这些元素的总和等于某个数字 S

我将使用该函数创建的列表来检查一些我认为是另一种任务的条件。现在，我正在寻找一种有效的方法来完成上述任务！我尝试使用蛮力，但我猜时间复杂度呈指数增长！

伪代码或已知算法的建议对我来说也很好！我只是一个建议，谢谢。

例如，

def f(end, S):
   #definition of the function

input f(14, 14)
output [14, 0, 0, 0, 0, 0] [0, 14, 0, 0, 0, 0] ...(and so on)... [0, 0, 3, 0, 7, 4] [0, 0, 3, 0, 6, 5] (and so on)...

以下是我上面提到的情况的信息，我的主要问题还是关于上面的任务！所以你可以忽略下面的部分

我有三个不同的函数，return 一个字符串（唯一可能的输出是 A、B、C 或（none）。例如）f1(list) --> 'A' f2(列表) --> 'B' f3(列表) --> 'C'

我会把我要求的函数创建的列表放到那些函数中，找出哪些情况的列表导致三个函数return一个不同的String，而它们都没有return (none)(f1, f2, f3 应该 return A 或 B 或 C)。我会对每个列表做一个循环，找出符合这个条件的。

Answer 1

你可以做到 -

def f(Num, List):
    n = Num 
    l = List 
    for i in range(len(List)):
        if len(List) > 0 and len(List) != 1:
            x= List.pop(0)
            y= List.pop(0)
            if x + y == Num:
                print(str(x) + " and " + str(y) + " are a sum of " + str(Num))  
        else:
            # print("the list has no more values")
            exit(0)

f(10, [5, 5, 8, 2, 3, 4, 3]) # 3, 4, 3 will not be checked

3,4,3不会被查的原因是因为程序不支持超过2个数字的和，想象一下如果你给出这个列表[4,4,2]并且想找到10作为其总和，该程序将不执行任何操作并退出，因为它不支持 3 个或更多数字。

Answer 2

Python 有一个广泛的标准库，它非常快速和有用。在这种情况下，itertools' combinations_with_replacement 就可以了。

您只需选择总和为 N

的组合

比如这段代码

import itertools as it

N = 14
SIZE = 6

lst = range(N+1)
sum_n_combs = [
    comb for comb in it.combinations_with_replacement(lst, SIZE)
    if sum(comb) == N
]
print(sum_n_combs)

产生

[(0, 0, 0, 0, 0, 14), (0, 0, 0, 0, 1, 13), (0, 0, 0, 0, 2, 12), (0, 0, 0, 0, 3, 11), (0, 0, 0, 0, 4, 10), (0, 0, 0, 0, 5, 9), (0, 0, 0, 0, 6, 8), (0, 0, 0, 0, 7, 7), (0, 0, 0, 1, 1, 12), (0, 0, 0, 1, 2, 11), (0, 0, 0, 1, 3, 10), (0, 0, 0, 1, 4, 9), (0, 0, 0, 1, 5, 8), (0, 0, 0, 1, 6, 7), (0, 0, 0, 2, 2, 10), (0, 0, 0, 2, 3, 9), (0, 0, 0, 2, 4, 8), (0, 0, 0, 2, 5, 7), (0, 0, 0, 2, 6, 6), (0, 0, 0, 3, 3, 8), (0, 0, 0, 3, 4, 7), (0, 0, 0, 3, 5, 6), (0, 0, 0, 4, 4, 6), (0, 0, 0, 4, 5, 5), (0, 0, 1, 1, 1, 11), (0, 0, 1, 1, 2, 10), (0, 0, 1, 1, 3, 9), (0, 0, 1, 1, 4, 8), (0, 0, 1, 1, 5, 7), (0, 0, 1, 1, 6, 6), (0, 0, 1, 2, 2, 9), (0, 0, 1, 2, 3, 8), (0, 0, 1, 2, 4, 7), (0, 0, 1, 2, 5, 6), (0, 0, 1, 3, 3, 7), (0, 0, 1, 3, 4, 6), (0, 0, 1, 3, 5, 5), (0, 0, 1, 4, 4, 5), (0, 0, 2, 2, 2, 8), (0, 0, 2, 2, 3, 7), (0, 0, 2, 2, 4, 6), (0, 0, 2, 2, 5, 5), (0, 0, 2, 3, 3, 6), (0, 0, 2, 3, 4, 5), (0, 0, 2, 4, 4, 4), (0, 0, 3, 3, 3, 5), (0, 0, 3, 3, 4, 4), (0, 1, 1, 1, 1, 10), (0, 1, 1, 1, 2, 9), (0, 1, 1, 1, 3, 8), (0, 1, 1, 1, 4, 7), (0, 1, 1, 1, 5, 6), (0, 1, 1, 2, 2, 8), (0, 1, 1, 2, 3, 7), (0, 1, 1, 2, 4, 6), (0, 1, 1, 2, 5, 5), (0, 1, 1, 3, 3, 6), (0, 1, 1, 3, 4, 5), (0, 1, 1, 4, 4, 4), (0, 1, 2, 2, 2, 7), (0, 1, 2, 2, 3, 6), (0, 1, 2, 2, 4, 5), (0, 1, 2, 3, 3, 5), (0, 1, 2, 3, 4, 4), (0, 1, 3, 3, 3, 4), (0, 2, 2, 2, 2, 6), (0, 2, 2, 2, 3, 5), (0, 2, 2, 2, 4, 4), (0, 2, 2, 3, 3, 4), (0, 2, 3, 3, 3, 3), (1, 1, 1, 1, 1, 9), (1, 1, 1, 1, 2, 8), (1, 1, 1, 1, 3, 7), (1, 1, 1, 1, 4, 6), (1, 1, 1, 1, 5, 5), (1, 1, 1, 2, 2, 7), (1, 1, 1, 2, 3, 6), (1, 1, 1, 2, 4, 5), (1, 1, 1, 3, 3, 5), (1, 1, 1, 3, 4, 4), (1, 1, 2, 2, 2, 6), (1, 1, 2, 2, 3, 5), (1, 1, 2, 2, 4, 4), (1, 1, 2, 3, 3, 4), (1, 1, 3, 3, 3, 3), (1, 2, 2, 2, 2, 5), (1, 2, 2, 2, 3, 4), (1, 2, 2, 3, 3, 3), (2, 2, 2, 2, 2, 4), (2, 2, 2, 2, 3, 3)]

查找总和为特定数字的数字列表的算法

Algorithm to find a list of numbers that sum up to a certain number

python

sum

list

set