Python - How to sum all combinations of a list of numbers in order to reach a goal. Use of number is optional

Question

I have a list of numbers

lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]

that I would like to sum in various ways in order to try and reach the goal number of 8276. I also need to see whether throwing away the cents or rounding helps reaching the goal. Note that use of a number is optional.

I tried

from itertools import combinations
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]
for i in xrange(1, len(lis) + 1):   #xrange will return the values 1,2,3,4 in this loop
    if sum(list(combinations(lis, i))) == 8276:
       print list(combinations(lis, i))

but this gives me

TypeError: unsupported operand type(s) for +: 'int' and 'tuple'

which I'm not sure why or how to fix.

Answer 1

Here is a solution if you want to consider the cases where you can throw away the cents, or you can round to the nearest whole number. This requirement turned a simple solution to a pretty complicated one. In order to account for the above requirement, I expanded each number to include the additional possible cases. The expanded list shows the new list to get the combinations:

import math
import itertools as it
tolerance = 150
target_sum = 8392
found = False
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]

def add_throw_and_round(num):
    num_list = [num]
    if int(num) != float(num):
        num_list.append(math.floor(num))
    if round(num) not in num_list:
        num_list.append(round(num))
    return sorted(num_list)

lis_expanded = map(add_throw_and_round, lis)
print "Expanded list:\n", lis_expanded, "\n\nTarget sum:\n", target_sum, "\n"
for n in range(1,len(lis) + 1):  # n is number of summands in pick
    lis_combos = it.combinations(lis_expanded, n)
    for lis_combo_n in lis_combos:
        for combo_n in (it.product(*lis_combo_n)):
            sum_ = sum(combo_n)
            if sum_ == target_sum:
                found = True
                answer = combo_n
            if sum_ > target_sum - tolerance and sum_ < target_sum + tolerance:
                print "sum:", sum_, "\tCombination: ", combo_n
if found:
    print "\nThere is a match: ", answer
else:
    print "\nNo exact match found"

So I decided to show all sums that was within 150 of the target sum, just to see if it was working. There were no matches were the sum was exactly 8276:

>>> 
===== RESTART: C:/Users/Joe/Desktop/scripts/Stack_overflow/cents_py2.py =====

Expanded list:
[[497.0, 497.96, 498.0], [10], [5084], [156.0, 156.43], [381.0, 381.3], [3298.0, 3298.85, 3299.0], [625.0, 625.68, 626.0]] 

Target sum:
8276 

sum: 8382.0     Combination:  (5084, 3298.0)
sum: 8382.85    Combination:  (5084, 3298.85)
sum: 8383.0     Combination:  (5084, 3299.0)
sum: 8392.0     Combination:  (10, 5084, 3298.0)
sum: 8392.85    Combination:  (10, 5084, 3298.85)
sum: 8393.0     Combination:  (10, 5084, 3299.0)

No exact match found
>>> 

Notice above that it tests cases where cents are thrown out, and rounded. Just to test whether it will report a match when the target sum does match, I tried target_sum = 8392 because the output shows one combination should match it. So here is the output in that case:

>>> 
===== RESTART: C:/Users/Joe/Desktop/scripts/Stack_overflow/cents_py2.py =====
Expanded list:
[[497.0, 497.96, 498.0], [10], [5084], [156.0, 156.43], [381.0, 381.3], [3298.0, 3298.85, 3299.0], [625.0, 625.68, 626.0]] 

Target sum:
8392 

sum: 8382.0     Combination:  (5084, 3298.0)
sum: 8382.85    Combination:  (5084, 3298.85)
sum: 8383.0     Combination:  (5084, 3299.0)
sum: 8392.0     Combination:  (10, 5084, 3298.0)
sum: 8392.85    Combination:  (10, 5084, 3298.85)
sum: 8393.0     Combination:  (10, 5084, 3299.0)
sum: 8538.0     Combination:  (5084, 156.0, 3298.0)
sum: 8538.85    Combination:  (5084, 156.0, 3298.85)
sum: 8539.0     Combination:  (5084, 156.0, 3299.0)
sum: 8538.43    Combination:  (5084, 156.43, 3298.0)
sum: 8539.28    Combination:  (5084, 156.43, 3298.85)
sum: 8539.43    Combination:  (5084, 156.43, 3299.0)

There is a match:  (10, 5084, 3298.0)
>>> 

Answer 2

Since you mention:

I also need to see whether throwing away the cents or rounding helps reaching the goal.

..the code below will show the closest n- combinations, and the absolute difference they show to the targeted number.

Works on both python3and python2

from itertools import combinations
# set the number of closest combinations to show, the targeted number and the list
show = 5
target = 8276
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]

diffs = []
for n in range(1, len(lis)+1):
    numbers = combinations(lis, n)
    # list the combinations and their absolute difference to target
    for combi in numbers:
        diffs.append([combi, abs(target - sum(combi))])

diffs.sort(key=lambda x: x[1])

for item in diffs[:show]:
    print(item[0], round(item[1],10))

The output will show the top- n closest combinations (combination / absolute difference to the targeted number):

(5084, 3298.85) 106.85
(10, 5084, 3298.85) 116.85
(5084, 156.43, 3298.85) 263.28
(10, 5084, 156.43, 3298.85) 273.28
(5084, 381.3, 3298.85) 488.15

This shows that the closest you can get is (5084, 3298.85), showing a difference of 106.85.

---

Note

See btw Note on floating point calculation:

---

Edit

For the sport of it, a condensed version of the above script:

from itertools import combinations 
# set the number of closest combinations to show, the targeted number and the list
show = 5
target = 8276
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]

diffs = [item for sublist in [[
    [combi, abs(target - sum(combi))] for combi in combinations(lis, n)
     ] for n in range(1, len(lis)+1)] for item in sublist]

diffs.sort(key=lambda x: x[1])
[print(item[0], round(item[1],10)) for item in diffs[:show]]

Answer 3

You're trying to sum all the combinations with given length instead of calculating a sum of a single combination. Instead you should loop over the combinations and check the sum for each one:

from itertools import combinations
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]
for i in xrange(1, len(lis) + 1):
    for comb in combinations(lis, i):
       if sum(comb) == 8276:
           print comb

The reason for the specific error is that sum takes optional argument start which is the default value. If argument is not provided it defaults to 0. Essentially your original code is trying to do following:

>>> sum([(1,), (2,)])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'int' and 'tuple'