Сумма элементов подмассивов равна целевому значению в Python

Question

Мне дают массив arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] и целевое значение trgt = 10.Мне нужно найти все возможные комбинации subarrays, чтобы сумма элементов каждого подмассива приводила к заданному целевому значению trgt.Мне нужно использовать Python для выполнения задачи.Я нашел подобное обсуждение в здесь .Однако данное решение там возвращает только один возможный подмассив вместо других допустимых подмассивов.Любая помощь, указывающая на получение всех таких подмассивов, будет очень полезна.Заранее спасибо.

Answer 1

Это функция @harry на SO-сайте вашей ссылки:

def subset(array, num):
    result = []
    def find(arr, num, path=()):
        if not arr:
            return
        if arr[0] == num:
            result.append(path + (arr[0],))
        else:
            find(arr[1:], num - arr[0], path + (arr[0],))
            find(arr[1:], num, path)
    find(array, num)
    return result

Это ваши данные:

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

функция сверху, примененная к вашим данным:

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

Поэтому я бы посоветовал вам перейти по ссылке, ответить на вопрос Гарри и использовать ее.

Answer 2

Библиотека выбора для получения комбинаций: itertools:

import itertools as it
import numpy as np

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

Сначала вычислите максимальную длину кортежа, которая может привести к trgt при суммировании, даже если он состоит изНаименьшие доступные числа:

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

Затем выполните итерацию от одного до maxsize, пусть itertools создает соответствующие комбинации и сохраняет только те, которые в сумме составляют 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)]

Answer 3

Поскольку вам нужно генерировать все решения, вы должны решить это, используя грубую силу.Один из способов сделать это - использовать битовую маскировку, как показано ниже

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n = len(arr)
target = 10
res = []
for i in range(1<<n):
    s = 0
    subset = []
    for j in range(n):
        if i & (1<<(j)): # if this bit is set to 1
            subset.append(arr[j])
    if sum(subset) == target:
        res.append(subset)
print(res)  # [[1, 2, 3, 4], [2, 3, 5], [1, 4, 5], [1, 3, 6], [4, 6], [1, 2, 7], [3, 7], [2, 8], [1, 9], [10]]

Answer 4

Следующее решение находит подмножества, которые добавляют к целевому номеру:

def subsetsum(array,num):

if num == 0 or num < 1:
    return None
elif len(array) == 0:
    return None
else:
    if array[0] == num:
        return [array[0]]
    else:
        with_v = subsetsum(array[1:],(num - array[0])) 
        if with_v:
            return [array[0]] + with_v
        else:
            return subsetsum(array[1:],num)