Python findPairs solving problem of finding sum

Question

I'm trying to extend the code below so that it shows me more than two values that make up a selected sum.

For example, given the numbers:

1.5, 5.4, -3.7, 7.4, 9.1, 28.1, 77.88, 39

I want to find out which of these numbers make up the sum, e.g.

129.68

(i.e. the code will read off the values that make up the: -3.7 + 7.4 + 9.1 + 77.88 + 39) = 129.68

The current code shows only two of the values, and though it doesn't always work, I think the problem is in the findPairs formula.

I'm looking for this because I don't really know which values make up the choosen sum. (It's something similar to Excel's solver, but it's very slow when I input a large number of values.)

Here is my code:

from collections import Counter
  
def findPairs(lst, K): 
    res = []
    count = Counter(lst)
  
    for x in lst:
        y = K - x
        if (x != y and count[y]) or (x == y and count[y] > 1):
            res.append((x, y)) 
            count.subtract((x, y))
              
    return res
      
# Driver code
lst = [1.5, 5.4, -3.7, 7.4, 9.1, 28.1, 77.88, 39]
K = 6.9
print(findPairs(lst, K))


Result

[(1.5, 5.4)]
>>>

Using floating points for this seems kind of risky see [here](https://stackoverflow.com/questions/588004/is-floating-point-math-broken). Perhaps you might want to use the `Fraction` class? — BrokenBenchmark, Apr 30 '22 at 06:01

Mário César Fracalossi Bais · Answer 1 · 2022-04-30T12:30:38.753

First, calculate all possible combinations, using library itertools:

`
def findComb(lst, sum_search):
    from itertools import combinations
    from math import fsum
    tolerance = 0.001
    # https://stackoverflow.com/questions/588004/is-floating-point-math-broken
    c = (combinations(lst, x) for x in range(1, len(lst)+1))
    # calculated all possible combinations

    return [tup for row in c for tup in row if abs(fsum(list(tup)) - sum_search) < tolerance]

sum_search = 129.68
lst = [1.5, 5.4, -3.7, 7.4, 9.1, 28.1, 77.88, 39]
print(findComb(lst, sum_search))
`

After that, program iterates and calculates the sum for each combination. Thanks for tolerance observation!

Python findPairs solving problem of finding sum

1 Answers1