且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

子数组元素的总和等于 Python 中的目标值

更新时间:2023-02-10 10:08:25

获取组合的首选库是 itertools:

The library of choice for getting combinations is itertools:

import itertools as it
import numpy as np

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
trgt = 10

首先计算可能导致 trgt 的元组的最大长度,即使它由可用的最小数字组成:

At first calculate the maximum length of a tuple that could result in trgt when summed up, even when it consists of the smallest numbers available:

maxsize = np.argwhere(np.cumsum(sorted(arr))>trgt)[0][0]

然后从1迭代到maxsize,让itertools创建对应的组合,只保存那些和trgt的组合:

Then iterate from one to maxsize, let itertools create the corresponding combinations and save only those which sum up to trgt:

subsets = []
for size in range(1, maxsize+1):
    subsets.extend([t for t in it.combinations(arr, size) if sum(t)==trgt])

print(subsets)

#[(10,), (1, 9), (2, 8), (3, 7), (4, 6), (1, 2, 7), (1, 3, 6), (1, 4, 5), (2, 3, 5), (1, 2, 3, 4)]