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

  • 12 сентября 2023 г. 5:36
Ответы на вопрос 2
Для составления комбинаций из чисел списка слагаемых, нужно использовать метод перебора всех возможных комбинаций.

Если нужно найти два слагаемых из списка {2, 1, 5, 8}, которые в сумме дают число 6, можно перебрать все возможные комбинации двух чисел и проверять их сумму:

1. 2 + 1 = 3 (не равно 6)
2. 2 + 5 = 7 (не равно 6)
3. 2 + 8 = 10 (не равно 6)
4. 1 + 5 = 6 (равно 6)

Таким образом, числа 1 и 5 из списка {2, 1, 5, 8} в сумме дают число 6.
Я рекомендую решить задачу с использованием рекурсии. У тебя есть два варианта:

1) Если раскладываемое число есть в списке, то это число будет единственным слагаемым.

2) Если раскладываемого числа нет в списке, то последовательно перебирай числа из списка, которые меньше раскладываемого числа. Эти числа могут быть возможными слагаемыми. 

При нахождении такого числа:

1) Вычитай его из раскладываемого числа.

2) Удали его и все предшествующие числа из списка.

3) Попробуй решить задачу для нового раскладываемого числа и нового списка чисел.

4) Если получено решение, возвращай результат, добавив к нему слагаемое, которое обрабатывалось.

Функция для решения этой задачи может выглядеть так:

def sum_split(summa: int, candidates: list[int]) -> list[int]:
    Если summa присутствует в candidates, то возвращай [summa].

    Иначе, для каждого числа candidates[i] перебирай числа:

    - Делай рекурсивный вызов answer = sum_split(summa - candidates[i], candidates[i+1:]).

    - Если список answer не пустой, добавляй к нему candidates[i] и возвращай его.

    - Если перебран весь список и ничего не подошло, возвращай пустой список.

Дальше работай с этим кодом как требуется.
Похожие вопросы