I have an arbitrary list of positive integers and some number X. I want to check if it is possible to retrieve X using basic operations such as summation and difference.
Any number from the list can be used only once. There might be duplicates.
We can use any amount of numbers from the list to get X, i.e. we can use just one element, two elements also can be used and it is possible to use all elements from the list.
Only True/False answer is enough.
E. g.:
input_list=[1, 7, 3]
X = 4
result: TRUE (e.g.: 7-3)
input_list=[1, 7, 3]
X = 50
result: FALSE
I have attempted to utilize the approach from this question: Find all combinations of a list of numbers with a given sum,
specifically this part:
[seq for i in range(len(numbers), 0, -1)
for seq in itertools.combinations(numbers, i)
if sum(seq) == target]
My idea was to concat the initial list with the list of the opposite integers:
new_list = input_list+list(map(lambda x: -x, input_list))
Then I'm checking if the list comprehension operation described above returns non empty list.
But this takes too much time, what I do not like is that there is some sort of duplication in this approach, itertools.combinations may take 1 and it's opposite -1 twice, but I have no idea how to fix that.
What is the most effecient way of solving such problem?
For each number in the list, you have to make a decision whether:
Here is a solution with breadth-first search of the decision tree:
def isRepresentable(input_list, num):
reachable = { 0 }
for n in input_list:
reachable = { y for x in reachable for y in [x, x + n, x - n] }
if num in reachable:
return True
return False
print(isRepresentable([1, 7, 3], 4)) # True
print(isRepresentable([1, 7, 3], 50)) # False
print(isRepresentable([1, 7, 3], 5)) # True
The BFS finds the shorter solutions, but DFS should be fine as well for true / false answers.
If one also wants to see how the number can be constructed, one has to save the path that lead to that number:
def findRepresentation(input_list, num):
reachable = { 0: [] }
for n in input_list:
next_reachable = dict(reachable)
for x in reachable:
for y in [x, x + n, x - n]:
if y not in next_reachable:
next_reachable[y] = [*(reachable[x]), y - x]
if num == y:
return next_reachable[y]
reachable = next_reachable
return None
def explain(input_list, num):
print(f'Using {input_list}')
print(f'{num} = {findRepresentation(input_list, num)}')
explain([1, 7, 3], 4) # 4 = [1, 3]
explain([1, 7, 3], 50) # None
explain([1, 7, 3], 5) # 5 = [1, 7, -3]
hundred_primes = [
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97, 101, 103, 107,
109, 113, 127, 131, 137, 139, 149, 151,
157, 163, 167, 173, 179, 181, 191, 193,
197, 199, 211, 223, 227, 229, 233, 239,
241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337,
347, 349, 353, 359, 367, 373, 379, 383,
389, 397, 401, 409, 419, 421, 431, 433,
439, 443, 449, 457, 461, 463, 467, 479,
487, 491, 499, 503, 509, 521, 523, 541
]
explain(hundred_primes, 2024)
Not that anybody asked, but 2024 can be represented as the sum of the first 33 prime numbers if one skips 103:
2024 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 107, 109, 113, 127, 131, 137, 139]