Как составить число n из элементов списка?

Question

[Onigire]

есть число n и список разных чисел. Необходимо узнать, можно ли среди этих чисел собрать число n, и если да, то заменить все слагаемые на их сумму.
(Если существует несколько вариантов комбинаций, то в приоритете суммировать бóльшие числа друг с другом)
То есть

n = 5
numbers = [1,1,2,4,7,9,1] 
#some code
numbers = [1,1,2,5,7,9]

Каков алгоритм?

Answer 1

[Vindicar]

Я бы решал задачу рекурсивно.
Найди в списке все числа x, меньшие или равные n, определи их позиции в списке, отсортируй по убыванию числа.
Если в списке есть x, равное n, ответ найден.
Иначе перебирай числа по порядку, от больших к меньшим, и для каждого числа x пробуй убрать его из списка, а потом рекурсивно решить задачу для суммы n-x.
Т.е. что-то типа:

def compose_sum(numbers: list[int], total: int) -> list[int] | None:
    # ищем индексы потенциальных слагаемых
    indices = [i for i in range(len(numbers)) if numbers[i] <= total] 
    # сортируем по убыванию слагаемых, потом по порядку в списке
    indices.sort(key = lambda i: (numbers[i], i), reverse=True)
    # если нулевой элемент совпадает - мы нашли точную сумму. Прерываем рекурсию.
    if numbers[indices[0]] == total: 
        return [indices[0]]
    for index in indices: # иначе перебираем слагаемые
        numcopy = numbers.copy()
        # копия списка без рассматриваемого слагаемого
        current = numpcopy.pop(index)
        next_indices = compose_sum(numcopy, total - current)
        if next_indices:  # нашли решение, корректируем индексы (так как мы удалили один элемент)
            for i in range(len(next_indices)):
                if next_indices[i] >= index:
                    next_indices[i] += 1
            return [index] + next_indices # отдаём наше решение "наверх"
        # next_indices пуст/None - решения не нашли, пробуем другой index
    return None # не нашли решения ни для одного index

Answer 2

[Roman K]

Изучай https://docs.python.org/3/library/itertools.html