Как проверить, можно ли получить какое-то число в результате суммирования или разности заданных чисел ⇐ Python

[Anonymous]

У меня есть произвольный список положительных целых чисел и некоторое число X. Я хочу проверить, можно ли получить X с помощью основных операций, таких как суммирование и разность.
Любое число из список можно использовать только один раз. Могут быть дубликаты.
Для получения X мы можем использовать любое количество чисел из списка, т.е. мы можем использовать только один элемент, также можно использовать два элемента и можно использовать все элементы из списка.
Достаточно только ответа «Верно/Неверно».
E. г.:

Код: Выделить всё

input_list=[1, 7, 3]
X = 4

результат: TRUE (например: 7-3)

Код: Выделить всё

input_list=[1, 7, 3]
X = 50

результат: ЛОЖЬ
Я попытался использовать подход из этого вопроса: найти все комбинации списка чисел с заданная сумма,
конкретно эта часть:

Код: Выделить всё

[seq for i in range(len(numbers), 0, -1)
for seq in itertools.combinations(numbers, i)
if sum(seq) == target]

Моя идея заключалась в том, чтобы объединить исходный список со списком противоположных целых чисел:

Код: Выделить всё

new_list = input_list+list(map(lambda x: -x, input_list))

Затем я проверяю, возвращает ли описанная выше операция понимания списка непустой список.
Но это занимает слишком много времени, чего я не делаю например, в этом подходе есть какое-то дублирование, itertools.combinations может дважды принимать 1 и противоположное -1, но я понятия не имею, как это исправить.
В чем проблема? наиболее эффективный способ решения такой проблемы?

Подробнее здесь: https://stackoverflow.com/questions/786 ... ation-or-d