子数组元素的总和等于 Python 中的目标值 [英] Sum of elements of subarrays is equal to a target value in Python

问题描述

我得到一个数组 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 和一个目标值 trgt = 10.我需要找到 subarrays 的所有可能组合，这样每个子数组的元素总和将产生给定的目标值 trgt.我需要使用 Python 来完成任务.我在 here 中发现了类似的讨论.然而，给定的解决方案只返回一个可能的子数组，而不是其他有效的子数组.任何指向获取所有此类子数组的帮助都将非常有帮助.提前致谢.

I am given with an array arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and a target value trgt = 10. I need to find all possible combinations of subarrays such that sum of the elements of each subarray will result in the given target value trgt. I need to use Python to acomplish the task. I have found a similar discussion in here. However the given solution there only returns only one possible subarray instead of other valid subarrays. Any help pointing to obtaining all such subarrays will be very helpful. Thank you in advance.

推荐答案

获取组合的首选库是 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)]

这篇关于子数组元素的总和等于 Python 中的目标值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！