Алгоритм, который бы искал в массиве чисел те, из суммы которых можно получить заданное число?

Question

[nepp]

Как можно реализовать?

Например, число: 12
Массив из чисел: 6 2 4 9 11 3

Вывод: 6 2 4
Если комбинаций несколько, выводит любую

Comments

[Max]

на каком языке

[Алан Гибизов]

Сам-то пытался? Покажи попытки.

[nepp]

Maxim Siomin, питон, с++, паскаль - любой

[nepp]

Maxim Siomin, или на словах объясни

[Max]

nepp, щас код на питоне напишу

[Max]

nepp, щас твой вопрос забанят. кинь свой email сюда. туда напишу

[nepp]

Maxim Siomin, [e-mail]

[Hemul GM]

Maxim Siomin, ты это зря. Ты в данной ситуации ни кому не помогаешь.

[Max]

nepp, ок. жди

[n1ksON]

nepp, можно так: берём первый элемент массива, начинаем суммировать: первый + второй + ... + Nный, до тех пор, пока сумма не станет больше заданного числа. Если стала больше, а сумма не найдена, то вычитаем последний элемент, который был сложен с общей суммой и пропуская его, начинаем суммировать дальше. И так, пока не будет найдена сумма.

Пример:
Ввод: 12
[5, 3, 2, 6, 4]
5 + 3 + 2 + 6 // сумма больше 12,
5 + 3 + 2 + 6 - 6 =>
5 + 3 + 2 + 4 // сумма больше 12, так как элемент последний, то начинаем с пропуском последнего элемента (да это повторение, но более оптимизированного варианта я не придумал), затем с пропуском предпоследнего и так далее
И так, рано или поздно, будет найдена сумма 5 + 3 + 4

[nepp]

Maxim Siomin, Спасибо!

Answer 1

[Max]

num = int(input())
numList = []
while True:
    num2 = input()
    if num2 != '':
        numList.append(int(num2))
    else:
        break
    

numList2 = []
for elem in numList:
    if num%elem == 0:
        numList2.append(elem)

for elem in numList2:
    print(elem)