0

Допустим, на вход даётся

[1, 2, 5, 3]

Нужно получить все возможные комбинации их сумм

На выходе

[3, 6, 4, 7, 5, 8, 8, 6, 9, 11]

Т.е:

1 + 2 = 3

1 + 5 = 6

1 + 3 = 4

2 + 5 = 7

2 + 3 = 5

5 + 3 = 8

...

(1+2) + 5 = 8

(1+2) + 3 = 6

(1+5) + 3 = 9

(1+2+5) + 3 = 11

Вот мой код написанный на питоне

for i in range(len(arr)):
firstEl = arr[i]
for j in range(len(arr) - 1):
    if arr[i] == arr[j+1]:
        pass
    else:
        arr.append(arr[i] + arr[j + 1])

Он работает не так, как нужно.

Он выводит(вывод я отсортировал и убрал повторяющиеся эл-ты):

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

4
  • Вот здесь вопрос о всех возможных произведениях. Понятно, что достаточно поменять умножение на сложение... :) Кстати, а почему у вас запрещена сумма 5+2? 3+2? 5+2+3?
    – Harry
    17 мар 2019 в 17:00
  • Это алгоритм, который (если я не ошибаюсь) будет иметь эффективность O(n!), откуда появляется вопрос... оно вам точно надо?
    – calm27
    17 мар 2019 в 17:00
  • @raviga при выполнении условия я выйду из цикла. Поэтому в худшем случае у него будет такая эффективность. 17 мар 2019 в 17:03
  • @Harry это моя ошибка) 17 мар 2019 в 17:04

1 ответ 1

2

Алгоритм со сложностью O(N*MaxSum).
Работает на принципе: сумму K можно составить из элемента cо значением item и суммы (K - item), если такая уже есть, набранная из других элементов. Цикл в обратном направлении позволяет избежать двойного использования элемента в сумме.

arr = [1, 3, 5, 8]
sm = sum(arr)
sums = set()
sums.add(0)

for item in arr:
    for k in range(sm, min(arr) - 1, -1):
        if (k - item) in sums:
            sums.add(k)
print(sums)

{0, 1, 3, 4, 5, 6, 8, 9, 11, 12, 13, 14, 16, 17}

Если сумма всех элементов велика, а самих элементов не так много, то выгоднее может быть использовать алгоритм генерации всех подмножеств и подсчёт их сумм со сложностью O(2^N)

11
  • извините, вы бы не могли подсказать, как заставить этот алгоритм работать пока не выполнится условие. Допустим, алгоритм прошёл первый круг, нашёл комбинации, как пойти по второму, третьему и т.д кругу, пока не будет выполнено определенное условие? 17 мар 2019 в 20:55
  • Какое условие? Если определённая сумма S, то нужно просто range с этой суммы начинать.
    – MBo
    18 мар 2019 в 1:48
  • @ MBo пользователь вводит число и мы должны перебирать все комбинации пока не найдем то число, которое делится на введённое число без остатка. Допустим [2,3,5] у меня останавливается на [2,3,5,7,8,10], а нужно, чтобы искалось ещё больше комбинаций, пока не поделится на 16(пример) без остатка. Должен получится [2,3,5,7,8,10,12,13,15,17,18,20...32] 18 мар 2019 в 6:27
  • В том месте, где sums.add(k) - проверять на делимость
    – MBo
    18 мар 2019 в 6:30
  • if k % 16 != 0: break ? 18 мар 2019 в 6:55

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.