How to check if the sum of 3 integers in the list matches another integer? (Python)

Question

Here is my problem:

I have a large integer (somewhere between 0 and 2 ^ 32-1). Let me call this number X. I also have a list of integers that are currently unsorted. All of them are unique numbers, greater than 0 and less than X. Suppose that in this list there are a large number of items, say more than 100,000 items.

I need to find up to 3 numbers in this list (let them be called A, B and C) that make up to X. A, B and C must be inside the list, and they can be repeated (for example, if X is 4, I I can have A = 1, B = 1 and C = 2, although 1 will only be displayed once in the list).

There may be several solutions for A, B and C, but I just need to find one possible solution for each of the fastest ways.

I tried to create a for loop structure like this:

For A in itemlist:
  For B in itemlist:
    For C in itemlist:
      if A + B + C == X:
        exit("Done")

But since my list of integers contains more than 100,000 elements, this uses too much memory and takes too much time.

Is there any way to find a solution for A, B, and C without using crazy amount of memory or taking crazy time? Thanks in advance.

Answer 1

you can reduce the runtime from n ^ 3 to n ^ 2 by using something like this

s = set(itemlist)
for A in itemlist:
    for B in itemlist:
        if X-(A+B) in s: 
            print A,B,X-(A+B)
            break

you can also sort the list and use binary search if you want to save memory

Answer 2

import itertools

nums = collections.Counter(itemlist)
target = t  # the target sum
for i in range(len(itemlist)):
    if itemlist[i] > target: continue
    for j in range(i+1, len(itemlist)):
        if itemlist[i]+itemlist[j] > target: continue
        if target - (itemlist[i]+itemlist[j]) in nums - collections.Counter([itemlist[i], itemlist[j]]):
            print("Found", itemlist[i], itemlist[j], target - (itemlist[i]+itemlist[j]))

Answer 3

@inspectorG4dget :

• C < B, .
• bisect_left() collections.Counter().

.

from random import randint
from bisect import bisect_left

X = randint(0, 2**32 - 1)
itemset = set(randint(0,X) for _ in range(100000))
itemlist = sorted(list(itemset))    # sort the list for binary search
l = len(itemlist)

for i,A in enumerate(itemlist):
    for j in range(i+1, l):         # use numbers above A
        B = itemlist[j]
        C = X - A - B               # calculate C
        if C <= B: continue    
        # see https://docs.python.org/2/library/bisect.html#searching-sorted-lists
        i = bisect_left(itemlist, C)
        if i != l and itemlist[i] == C:
            print("Found", A, B, C)

To reduce the number of comparisons, we apply A < B < C.