Дан массив целых чисел A. Требуется найти число различных сумм, составленных из части его элементов

Question

Дан массив целых чисел A. Требуется найти число различных сумм, составленных из части его элементов. Для массива [1,2,3] полный набор сумм — это [0, 1, 1+2, 1+3, 1+2+3, 2, 2+3, 3]. Различные суммы — это {0,1,2,3,4,5,6}. Итого 7 различных сумм. Ограничения: длина массива A не превышает 500, его элементы принимают значения от 0 до 100. Мой код:

def combinations(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

def sums(array: list) -> int:
    combs = []

    for i in range(2, len(array)+1):
        combs += list(combinations(array, i))

    sumsSet = set([0] + array + list(map(sum, combs)))

    return len(sumsSet)

print(sums([49, 100, 98, 49, 0]))

Для коротких входных массивов алгоритм работает быстро, а для больших, к примеру: [1, 2, 4, 8, 16, 32, 64] + [100] * 493 выполняется очень долго. Как я могу сократить время выполнения алгоритма?

Answer 1

вот такое скорее всего нужно?

array = [1, 2, 4, 8, 16, 32, 64] + [100] * 493

res = {0}

for num in array:
    res = set(list(res) + [(i + num) for i in res])

print(len(res))

или так:

res = {0}

for num in array:
    res.update([(i + num) for i in res])

БЛОГ НА HUSL

Дан массив целых чисел A. Требуется найти число различных сумм, составленных из части его элементов

Ответы (1 шт):