Как получить число s из суммы последовательности элементов n не импортируя библиотеки с комбинаторики

Question

у меня есть n чисел и число s которое надо получить складывая любые элементы последовательности из n чисел с друг другом , как подсчитать сколько таких сумм равных s существует в последовательности из n чисел. Вот мой вариант кода

n , s = map(int, input().split())
a = []
k=0
for i in range(n):
    a[i] = int(input())
    if a[i] + a[i] == s:
        ++k

print(k)

Answer 1

если я не путаю, а могу, то код должен быть такой:

сначала только надо собрать массив чисел и отсортировать их - это нужно для ускорения анализа, чтобы пропускать суммы, превышающие заданный предел иначе на каждой итерации надо рассматривать все числа, да еще держать где-то список чисел, которые уже в сумму участвуют, сортировка позволяет избавиться от этого геммороя

limit = 11

sequence = [5, 6, 1, 65, 12, 3, 5, 7, 2]

def calc(limit, sequence, start, sum, count):

    for pos in range(start, len(sequence)):

        # вычислить сумму
        sum_new = sum + sequence[pos]

        # если сумма больше предела - не рассматривать дальше, поскольку остальные суммы будут больше
        if sum_new > limit:
            break

        # если сумма равна пределу - увеличить счётчик 
        if sum_new == limit:
            count += 1

        # вычислить сумму
        count = calc(limit, sequence, pos + 1, sum_new, count)

    return count


# отсортировать последовательность чисел
sequence.sort()

# вычислить кол-во вариантов сумм
count = calc(limit, sequence, 0, 0, 0)

print(count)

На всякий случай можно посмотреть, а что же все таки находится:

debug = []

def calc(limit, sequence, start, sum, count, result):

    for pos in range(start, len(sequence)):

        # вычислить сумму
        sum_new = sum + sequence[pos]
        result_new = result + [sequence[pos]];

        # если сумма больше предела - не рассматривать дальше, поскольку остальные суммы будут больше
        if sum_new > limit:
            break

        # если сумма равна пределу - увеличить счётчик
        if sum_new == limit:
            debug.append(result_new)
            count += 1

        # вычислить сумму
        count = calc(limit, sequence, pos + 1, sum_new, count, result_new)

    return count


# отсортировать последовательность чисел
sequence.sort()

# вычислить кол-во вариантов сумм
count = calc(limit, sequence, 0, 0, 0, [])

print(*debug, sep="\n")

получается:

src:  [1, 2, 3, 5, 5, 6, 7, 12, 65]
[1, 2, 3, 5]
[1, 2, 3, 5]
[1, 3, 7]
[1, 5, 5]
[2, 3, 6]
[5, 6]
[5, 6]

есть повторяющиеся последовательности, но это потому, что есть одинаковые числа (например, 5)

БЛОГ НА HUSL

Как получить число s из суммы последовательности элементов n не импортируя библиотеки с комбинаторики

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