In SQL, find a combination of rows whose sum is summed up to a certain amount (or in another table)

Question

Table_1
Integer D_ID
Integer Deposit

Table_2
Total_ID
Total_amt integer

Is it possible to write a select statement to find all rows in Table_1whose sum Deposit_amtis equal Total_amtto Table_2. Both tables have several rows.

Say the first line in Table_2has Total_amt=100. I would like to know that in Table_1lines with D_ID2, 6, 12 summed = 100, lines D_ID2, 3, 42 summed = 100, etc.

Help evaluate. Let me know if I need to clarify.

I ask this question, since someone who enters into their work has a list of transactions and a list of totals, she needs to find a possible list of transactions that could create a total amount. I agree that this sounds dangerous, because finding a combination of transactions whose sum is summed up does not guarantee that they created a total amount.

I did not know that this is an np-complete problem.

Answer 1

Just for fun, I made a brute force decision. He will find combinations of one, two or three entries that make up Total_amt. You can expand it to process more transactions by the amount, adding swap d4, d5etc.:

begin tran

create table Table_1 (D_ID int, Deposit_amt int)
create table Table_2 (Total_ID int, Total_amt int)

insert into Table_1 (D_ID, Deposit_amt) values (1, 4)
insert into Table_1 (D_ID, Deposit_amt) values (2, 3)
insert into Table_1 (D_ID, Deposit_amt) values (3, 1)
insert into Table_1 (D_ID, Deposit_amt) values (4, 1)
insert into Table_1 (D_ID, Deposit_amt) values (5, 9)
insert into Table_1 (D_ID, Deposit_amt) values (6, 13)
insert into Table_1 (D_ID, Deposit_amt) values (7, 6)
insert into Table_1 (D_ID, Deposit_amt) values (8, 7)
insert into Table_1 (D_ID, Deposit_amt) values (9, 12)
insert into Table_1 (D_ID, Deposit_amt) values (10, 4)

insert into Table_2 (Total_ID, Total_amt) values (1, 17)
insert into Table_2 (Total_ID, Total_amt) values (2, 23)
insert into Table_2 (Total_ID, Total_amt) values (3, 55)
insert into Table_2 (Total_ID, Total_amt) values (4, 4)

select t.Total_amt, 
    d1.D_ID as d1_ID, d1.Deposit_amt as d1_amt, 
    d2.D_ID as d2_ID, d2.Deposit_amt as d2_amt, 
    d3.D_ID as d3_ID, d3.Deposit_amt as d3_amt
from Table_2 t
cross join (
    select D_ID, Deposit_amt from Table_1 
) d1
inner join (
    select D_ID, Deposit_amt from Table_1 
    union all
    select null, null
) d2 on d1.D_ID > d2.D_ID or d2.D_ID is null
inner join (
    select D_ID, Deposit_amt from Table_1 
    union all
    select null, null
) d3 on d2.D_ID > d3.D_ID or d3.D_ID is null
where isnull(d1.Deposit_amt, 0) + isnull(d2.Deposit_amt, 0) + isnull(d3.Deposit_amt, 0) = t.Total_amt
order by Total_amt

rollback tran

Output:

Total_amt   d1_ID       d1_amt      d2_ID       d2_amt      d3_ID       d3_amt
----------- ----------- ----------- ----------- ----------- ----------- -----------
4           3           1           2           3           NULL        NULL
4           4           1           2           3           NULL        NULL
4           1           4           NULL        NULL        NULL        NULL
4           10          4           NULL        NULL        NULL        NULL
17          9           12          3           1           1           4
17          9           12          4           1           1           4
17          10          4           5           9           1           4
17          8           7           7           6           1           4
17          6           13          1           4           NULL        NULL
17          10          4           6           13          NULL        NULL
17          10          4           8           7           7           6
17          8           7           5           9           4           1
17          10          4           9           12          4           1
17          8           7           5           9           3           1
17          10          4           9           12          3           1
17          6           13          3           1           2           3
17          6           13          4           1           2           3
23          8           7           6           13          2           3
23          6           13          5           9           3           1
23          6           13          5           9           4           1
23          10          4           7           6           6           13
23          10          4           9           12          8           7
23          7           6           6           13          1           4
23          9           12          8           7           1           4

(24 row(s) affected)

.. , Deposit_amt > Total_amt, , , , Deposit_amt .

Answer 2

..: p

Answer 3

CREATE TABLE #N1 (ID INT NOT NULL IDENTITY(1,1) PRIMARY KEY CLUSTERED, Val INT)
CREATE TABLE #N2 (ID INT NOT NULL IDENTITY(1,1) PRIMARY KEY CLUSTERED, Val INT)

-- SELECT TOP 20 'INSERT INTO #N1 (Val) VALUES (' + CAST (CAST (RAND (CAST (NEWID () AS VARBINARY) ) * 100 AS INT) AS VARCHAR) + ')' FROM sys.objects
INSERT INTO #N1 (Val) VALUES (93)
INSERT INTO #N1 (Val) VALUES (93)
INSERT INTO #N1 (Val) VALUES (86)
INSERT INTO #N1 (Val) VALUES (23)
INSERT INTO #N1 (Val) VALUES (51)
INSERT INTO #N1 (Val) VALUES (85)
INSERT INTO #N1 (Val) VALUES (93)
INSERT INTO #N1 (Val) VALUES (27)
INSERT INTO #N1 (Val) VALUES (12)
INSERT INTO #N1 (Val) VALUES (15)
INSERT INTO #N1 (Val) VALUES (23)
INSERT INTO #N1 (Val) VALUES (87)
INSERT INTO #N1 (Val) VALUES (94)
INSERT INTO #N1 (Val) VALUES (61)
INSERT INTO #N1 (Val) VALUES (15)
INSERT INTO #N1 (Val) VALUES (86)
INSERT INTO #N1 (Val) VALUES (38)
INSERT INTO #N1 (Val) VALUES (81)
INSERT INTO #N1 (Val) VALUES (67)
INSERT INTO #N1 (Val) VALUES (45)

-- SELECT TOP 20 'INSERT INTO #N2 (Val) VALUES (' + CAST (CAST (RAND (CAST (NEWID () AS VARBINARY) ) * 100 AS INT) AS VARCHAR) + ')' FROM sys.objects
INSERT INTO #N2 (Val) VALUES (32)
INSERT INTO #N2 (Val) VALUES (1)
INSERT INTO #N2 (Val) VALUES (24)
INSERT INTO #N2 (Val) VALUES (20)
INSERT INTO #N2 (Val) VALUES (40)
INSERT INTO #N2 (Val) VALUES (25)
INSERT INTO #N2 (Val) VALUES (37)
INSERT INTO #N2 (Val) VALUES (19)
INSERT INTO #N2 (Val) VALUES (47)
INSERT INTO #N2 (Val) VALUES (23)
INSERT INTO #N2 (Val) VALUES (7)
INSERT INTO #N2 (Val) VALUES (53)
INSERT INTO #N2 (Val) VALUES (75)
INSERT INTO #N2 (Val) VALUES (82)
INSERT INTO #N2 (Val) VALUES (15)
INSERT INTO #N2 (Val) VALUES (26)
INSERT INTO #N2 (Val) VALUES (22)
INSERT INTO #N2 (Val) VALUES (70)
INSERT INTO #N2 (Val) VALUES (17)
INSERT INTO #N2 (Val) VALUES (1)

SELECT #N1.ID, #N2.ID, t.Val1, t.Val2
FROM (
SELECT
  #N1.Val AS Val1
, #N2.Val AS Val2
FROM #N1,#N2
WHERE #N1.Val+#N2.Val=100
) AS t
INNER JOIN #N1 ON #N1.Val = t.Val1
INNER JOIN #N2 ON #N2.Val = t.Val2