In SQL find the combination of rows whose sum add up to a specific amount (or amt in other table)_问答_开发者

Table_1
D_ID Integer
Deposit_amt integer

Table_开发者_C百科2
Total_ID
Total_amt integer

Is it possible to write a select statement to find all the rows in Table_1 whose Deposit_amt sum to the Total_amt in Table_2. There are multiple rows in both tables.

Say the first row in Table_2 has a Total_amt=100. I would want to know that in Table_1 the rows with D_ID 2, 6, 12 summed = 100, the rows D_ID 2, 3, 42 summed = 100, etc.

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

I am asking this question as someone as part of their job has a list of transactions and a list of totals, she needs to find the possible list of transactions that could have created the total. I agree this sounds dangerous as finding a combination of transactions that sums to a total does not guarantee that they created the total.

I wasn't aware it is an np-complete problem.

Give your friend this, and wish her good luck .. :p

In SQL find the combination of rows whose sum add up to a specific amount (or amt in other table)

Just for fun I did a brute force solution. It will find combinations of one, two, or three records that add up to Total_amt. You could expand it to handle more transactions per sum, by adding d4, d5 subselects, etc.:

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)

Note: You could filter out individual rows whose Deposit_amt > Total_amt, but this would probably not help performance much unless Deposit_amt was indexed.

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

This is my approach in Oracle PLSQL,

select *
from Table_2 tt
cross join
(
select 
       a.deposit_amt as dep_one, 
       b.deposit_amt as dep_two,
       c.deposit_amt as dep_three
  from Table_1 a
 
 inner join (select * from Table_1 union all select null , null from dual)b
    on b.deposit_amt < a.deposit_amt
    or b.deposit_amt is null
 
 inner join (select * from Table_1 union all select null , null from dual)c
    on c.deposit_amt < b.deposit_amt
    or c.deposit_amt is null
  order by 1,2,3 asc
 ) p
where nvl(dep_one,0) + nvl(dep_two,0) + nvl(dep_three,0) = tt.total_amt
order by tt.total_amt