Python - How to sum all combinations of a list of numbers in order to reach a goal. Use of number is optional
<p>I have a list of numbers</p>

<pre><code>lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]
</code></pre>

<p>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.</p>

<p>I tried </p>

<pre><code>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))
</code></pre>

<p>but this gives me </p>

<pre><code>TypeError: unsupported operand type(s) for +: 'int' and 'tuple'
</code></pre>

<p>which I'm not sure why or how to fix.</p>

<p>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:</p>

<pre><code>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_ &gt; target_sum - tolerance and sum_ &lt; target_sum + tolerance:
                print "sum:", sum_, "\tCombination: ", combo_n
if found:
    print "\nThere is a match: ", answer
else:
    print "\nNo exact match found"
</code></pre>

<p>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:</p>

<pre><code>&gt;&gt;&gt; 
===== 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
&gt;&gt;&gt; 
</code></pre>

<p>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:</p>

<pre><code>&gt;&gt;&gt; 
===== 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)
&gt;&gt;&gt; 
</code></pre>

python sum combinations permutation