obtain all possible combinations that give a total

Question

I need to know how I can improve this code so that it shows me all the possible combinations of numbers that added together give the result I am looking for.

code

import itertools
lista=[95.95, 73.35, 78.85, 78.85, 22.85, 90.45, 64.15, 88.45, 37.12, 90.45, 37.12, 37.12, 95.95, 14.18, 78.85, 78.85, 64.15, 90.45, 90.45, 56.08, 66.75]

valor=662.25
# Generar todas las combinaciones posibles
combinations = []
for r in range(len(lista)):
    combinations += itertools.combinations(lista, r)

# Comprobar si la suma de cada combinación es igual a la suma objetivo
result = []
for combo in combinations:
    if sum(combo) == valor:
        result.append(combo)

# Mostrar las combinaciones encontradas
if result:
    for combo in result:
        print(combo)
else:
    print("no se encontraron resultados")

In this case, when I run the program it tells me that it does not find any solution but it really does and it is this: [22.85 , 90.45 , 88.45 , 90.45 , 37.12 , 95.95 , 90.45 , 90.45 , 56.08]

Answer 1

Your problem (now) is floating-point rounding error:

$ python
Python 3.8.10 (default, May 26 2023, 14:05:08) 
[GCC 9.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> a = [22.85 , 90.45 , 88.45 , 90.45 , 37.12 , 95.95 , 90.45 , 90.45 , 56.08]
>>> print(sum(a))
662.2500000000001

Note: that is not exactly 662.25 so your test using == is most likely failing.

This is NOT a python bug. Rather it is a consequence of how floating point arithmetic works on computers. For more information:

• Is floating point math broken?. (The short answer is "No". The long answer is many pages of mathematical analysis followed by "Therefore No".)
• What Every Computer Scientist Should Know About Floating-Point Arithmetic

There are two approaches to solving this "problem":

1. Do a range test; e.g. test that the absolute value of the difference between the two values is acceptably small:

   if abs(662.25 - sum(a)) < 0.005:
   

   This is a more Pythonic way:

   if round(sum(a), 2) == 662.25:
   

   (In general, the problem is knowing what the range test threshold should be. Since your numbers seem to have 2 digits precision after the decimal point, rounding to 2 digits is appropriate in your case.)

2. Do the arithmetic using (for example) decimal.Decimal. This will be more expensive, but you will get precise values. (Unless you do division operations ...)