How to find all combinations that equal a given sum?

Question

In SQL I have a list of transaction types and a value. Simple example below.

|-----------|--------|
| Tran.Type | Value  | 
|-----------|--------|
|     04    |   10   |
|-----------|--------|
|     07    |   10   |
|-----------|--------|
|     04    |   5    |
|-----------|--------|
|     01    |   8    | 
|-----------|--------|



|-----------------|
| Current Balance |
|-----------------|
|        13       |
|-----------------|

Goal is to sum values and get number 13. In this example is easy to find that type 07 is negative. So 10-10+5+8=13

But when number of transaction gets to 20 & 10 different types is quite difficult. Also values are positive & negative.

So far I came up with this.

import itertools
numbers = list(map(int, input("Enter multiple values: ").split()))
expectedSum = int(input("Enter expected value: "))
result = [seq for i in range(len(numbers), 0, -1) for seq in 
itertools.combinations(numbers, i) if sum(seq) == expectedSum]
print (result)<code>

Any idea how can I incorporate type to result section? and if that type is an opposite value or not?

This is an interesting question. It could be simplified by stripping the SQL out of the Q, which will narrow down the problem. Consider starting the question with say, a list of tuples containing only the transaction type and value. — TrebledJ, Jun 08 '19 at 16:50
I'm pretty sure this problem is NP-hard - looks like Knapsack problem: https://en.wikipedia.org/wiki/Knapsack_problem — eddiewould, Jun 10 '19 at 02:16
Maybe dupe: [How to find all combinations that sum up to at most a constant?](https://stackoverflow.com/q/46942681/674039) — wim, Jun 10 '19 at 02:29

Amitabh Das · Answer 1 · 2019-06-10T02:23:36.027

There are a couple of ways to do this, by using CASE in your SQL statement OR if you have a VERY large list then introduce a field which will contain +1 or -1 based on the Transaction Type, then when you are performing the values MULTIPLY the value and finally do a sum. Example, is here;

ALTER TABLE Tran ADD COLUMN tran_multiple INT default 1;

-- update each value as req.
UPDATE Tran set tran_multiple=-1 WHERE Tran.id = xxxx; 

SELECT sum (TranValue.Value * Tran.tran_multiple) as Val From TranValue 
    INNER JOIN Tran on TranValue.Type = Tran.Type

Here I am assuming that your table TranValue stores the values. Of course, you can use Group By clause GROUP BY Tran.type in your statement, along with Tran.type in your SELECT field list (for listing by Tran.Type & Values). Then writing a simple code should not be a problem.

Though, I would request you to refrain from using VALUE or VALUES in your SQL as it is very similar to the RESERVED KEYWORDs (just a suggestion)

I am not putting the CASE example here since you didn't specify which Database you are using (syntax varies) and also since you claim that there are a large number of types.

If you prefer coding instead of SQL, then the same can be done by defining a dictionary where each type holds +1 or -1 depending on the type and then when the user inputs the values you can multiply type and get it done.

Hope this helps.

How to find all combinations that equal a given sum?

1 Answers1