Чтобы найти в Python комбинации чисел, равные заданной сумме, можно использовать несколько методов. Вот несколько популярных подходов:

1. Метод грубой силы с использованием рекурсии:

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

2. Динамическое программирование (DP) с использованием мемоизации:

   • Используйте мемоизацию, чтобы сохранить ранее вычисленные результаты и избежать повторных вычислений.
   • Разбейте проблему на более мелкие подзадачи и итеративно постройте решение.
   • Этот подход имеет лучшую временную сложность, чем метод грубой силы.

3. Алгоритм возврата:

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

4. Использование комбинаций Itertools:

   • Используйте функцию combinationsиз модуля itertools, чтобы сгенерировать все возможные комбинации заданного списка чисел.
   • Проверьте, равна ли какая-либо из комбинаций желаемой сумме.

Вот пример метода грубой силы с использованием рекурсии:

def find_combinations(target_sum, numbers):
    def find_combinations_helper(target, current_combination, start_index):
        if target == 0:
            print(current_combination)
        elif target < 0:
            return
        else:
            for i in range(start_index, len(numbers)):
                find_combinations_helper(target - numbers[i], current_combination + [numbers[i]], i)
    find_combinations_helper(target_sum, [], 0)
# Example usage:
numbers = [2, 4, 6, 8]
target_sum = 10
find_combinations(target_sum, numbers)