Algorithm to find which number in a list sum up to a certain number

user_398749 0
Viewed 74419

I have a list of numbers. I also have a certain sum. The sum is made from a few numbers from my list (I may/may not know how many numbers it's made from). Is there a fast algorithm to get a list of possible numbers? Written in Python would be great, but pseudo-code's good too. (I can't yet read anything other than Python :P )

Example

list = [1,2,3,10]
sum = 12
result = [2,10]

NOTE: I do know of Algorithm to find which numbers from a list of size n sum to another number (but I cannot read C# and I'm unable to check if it works for my needs. I'm on Linux and I tried using Mono but I get errors and I can't figure out how to work C# :(
AND I do know of algorithm to sum up a list of numbers for all combinations (but it seems to be fairly inefficient. I don't need all combinations.)

pseudocode math algorithm python
5 Answers

I know I'm giving an answer 10 years later since you asked this, but i really needed to know how to do this an the way jbernadas did it was too hard for me, so i googled it for an hour and I found a python library itertools that gets the job done!

I hope this help to future newbie programmers. You just have to import the library and use the .combinations() method, it is that simple, it returns all the subsets in a set with order, I mean:

For the set [1, 2, 3, 4] and a subset with length 3 it will not return [1, 2, 3][1, 3, 2][2, 3, 1] it will return just [1, 2, 3]

As you want ALL the subsets of a set you can iterate it:

import itertools

sequence = [1, 2, 3, 4]
for i in range(len(sequence)):
    for j in itertools.combinations(sequence, i):
        print(j)

The output will be

() (1,) (2,) (3,) (4,) (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4) (1, 2, 3) (1, 2, 4) (1, 3, 4) (2, 3, 4)

Hope this help!

user_136537050

I have found an answer which has run-time complexity O(n) and space complexity about O(2n), where n is the length of the list.

The answer satisfies the following constraints:

  1. List can contain duplicates, e.g. [1,1,1,2,3] and you want to find pairs sum to 2

  2. List can contain both positive and negative integers

The code is as below, and followed by the explanation: 

def countPairs(k, a):
    # List a, sum is k
    temp = dict()
    count = 0
    for iter1 in a:
        temp[iter1] = 0
        temp[k-iter1] = 0
    for iter2 in a:
        temp[iter2] += 1
    for iter3 in list(temp.keys()):
        if iter3 == k / 2 and temp[iter3] > 1:
            count += temp[iter3] * (temp[k-iter3] - 1) / 2
        elif iter3 == k / 2 and temp[iter3] <= 1:
            continue
        else:
            count += temp[iter3] * temp[k-iter3] / 2
    return int(count)
  1. Create an empty dictionary, iterate through the list and put all the possible keys in the dict with initial value 0. Note that the key (k-iter1) is necessary to specify, e.g. if the list contains 1 but not contains 4, and the sum is 5. Then when we look at 1, we would like to find how many 4 do we have, but if 4 is not in the dict, then it will raise an error.
  2. Iterate through the list again, and count how many times that each integer occurs and store the results to the dict.

  3. Iterate through through the dict, this time is to find how many pairs do we have. We need to consider 3 conditions:

    3.1 The key is just half of the sum and this key occurs more than once in the list, e.g. list is [1,1,1], sum is 2. We treat this special condition as what the code does.

    3.2 The key is just half of the sum and this key occurs only once in the list, we skip this condition.

    3.3 For other cases that key is not half of the sum, just multiply the its value with another key's value where these two keys sum to the given value. E.g. If sum is 6, we multiply temp[1] and temp[5], temp[2] and temp[4], etc... (I didn't list cases where numbers are negative, but idea is the same.)

The most complex step is step 3, which involves searching the dictionary, but as searching the dictionary is usually fast, nearly constant complexity. (Although worst case is O(n), but should not happen for integer keys.) Thus, with assuming the searching is constant complexity, the total complexity is O(n) as we only iterate the list many times separately.

Advice for a better solution is welcomed :)

user_87402190
Related