Как я могу сложить номер списка

Question

Я ищу, как мне создать список из 6 чисел. И у меня есть число, которое я исследую, например 30, которое является результатом сложения с номером моего списка

Вот простой пример:

list=[]
list.append[1,5,5,10,8,2]

and the number that I want in rapport with the list is for example 30

Таким образом, решение будет 5 + 5 + 10 + 8 + 2 = 30

И он возвращает мне разные шаги, чтобы иметь 30

Конечно, у вас есть ограничение. Дело в том, что вы не можете использовать одно и то же число 2 раза, но вы можете сохранить результат, чтобы использовать его позже.

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

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

Я хотел бы, например, с моим примером моего списка выше:

1+5=6 # 30 so I continue, 6+5#11 so I continue ...  And at the end I need find the right way to find 30

Итак, вот решение:

5+5=10
10+10=20
20+8=28
28+2=30   and 30 is my research number so we stop the function and we print the steps to have the good solution.

Спасибо!

Answer 1

Вот подход с рекурсивной функцией генератора:

def sumto(n, lst):
    if not n and not lst:  # base case 1: empty list = 0
        yield []
        return
    if n < 0 or not lst:  # base case 2: unsolvable
        return
    head, *tail = lst
    for sol in sumto(n-head, tail):  # recursion 1: use first element
        yield [head] + sol
    yield from sumto(n, tail)  # recursion 2: don't use first element

>>> list(sumto(30, [1,5,5,10,8,2]))
[[5, 5, 10, 8, 2]]
>>> list(sumto(28, [1,5,5,10,8,2]))
[[5, 5, 10, 8]]
>>> list(sumto(42, [1,5,5,10,8,2]))
[]
>>> list(sumto(10, [1,5,5,10,8,2]))
[[5, 5], [10], [8, 2]]

Answer 2

Я думаю, что это классическая c проблема (я не помню названия), я написал для вас простое решение на основе обратного пути. Для этого должны быть лучшие (с точки зрения производительности) решения.

Вместо печати вы можете поместить ответ в глобальный список или вернуть его с небольшим трудом.

def sub(all_numbers: list, current_index: int, goal: int) -> bool:
    """
    Tries to construct goal using all_numbers[current_index:] if the goal can be reached it will print picked numbers
    and return True
    """
    if current_index >= len(all_numbers):
        return goal == 0
    if goal < 0:
        return False
    current = all_numbers[current_index]
    pick_current_result = sub(all_numbers, current_index + 1, goal - current)
    if pick_current_result:
        print(current)
        return True
    dont_pick_current_result = sub(all_numbers, current_index + 1, goal)
    return dont_pick_current_result


def solve(all_numbers: list, goal: int):
    sub(all_numbers, 0, goal)


solve([1, 5, 5, 10, 8, 2], 30)