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

Question

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

Answer 1

Библиотека выбора для получения комбинаций 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 2

Это функция @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 3

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

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)

Answer 4

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

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]]