sql server : select rows who's sum matches a value

Question

here is table T :-

and the following is a fictional sql

select *
from T
where sum(num) = '150'

the expected result is :-

(A)

id  num
-------
 1  50
 8  100

(B)

id  num
-------
 2  20
 7  30
 8  100

(C)

id  num
-------
 4  40
 5  10
 8  100

the 'A' case is most preferred !

i know this case is related to combinations.

in real world - client gets items from a shop, and because of an agreement between him and the shop, he pay every Friday. the payment amount is not the exact total of items for example: he gets 5 books of 50 € ( = 250 € ), and on Friday he bring 150 €, so the first 3 books are perfect match - 3 * 50 = 150. i need to find the id's of those 3 books !

any help would be appreciated!

Or `(3,90);(6,60)`, or `(9,70);(10,80)`, why is the first option the "most preferred"? — Lamak, Jan 09 '14 at 12:49
I think this problem requires an iterative approach, which is not SQL's strongest suit. — Andriy M, Jan 09 '14 at 12:56
http://stackoverflow.com/questions/2255908/in-sql-find-the-combination-of-rows-whose-sum-add-up-to-a-specific-amount-or-am — Mikael Eriksson, Jan 09 '14 at 13:13
@Lamak the first option is the "most preferred" because it has less rows. but it's optional — armen, Jan 09 '14 at 13:19
As @Lamak said: A combination between `3 (90) and 6 (60)`, `9 (70) and 10(80)` would result in 2 rows, too. — Kiril Rusev, Jan 09 '14 at 13:27
oh, my mistake, any of those would do the job. the point is to have the minimal number of rows. — armen, Jan 09 '14 at 13:35

score 3 · Accepted Answer · answered Jan 09 '14 at 13:59

You can use recursive query in MSSQL to solve this.

SQLFiddle demo

The first recursive query build a tree of items with cumulative sum <= 150. Second recursive query takes leafs with cumulative sum = 150 and output all such paths to its roots. Also in the final results ordered by ItemsCount so you will get preferred groups (with minimal items count) first.

WITH CTE as
( SELECT id,num,
         id as Grp,
         0 as parent,
         num as CSum,
         1 as cnt,
         CAST(id as Varchar(MAX)) as path
     from T where num<=150
  UNION all
  SELECT t.id,t.num,
         CTE.Grp as Grp, 
         CTE.id as parent,
         T.num+CTE.CSum as CSum,
         CTE.cnt+1 as cnt,
         CTE.path+','+CAST(t.id as Varchar(MAX)) as path
    from T 
  JOIN CTE on T.num+CTE.CSum<=150 
             and CTE.id<T.id 
),
BACK_CTE as
(select CTE.id,CTE.num,CTE.grp, 
         CTE.path ,CTE.cnt as cnt,
         CTE.parent,CSum 
    from CTE where CTE.CSum=150
  union all
  select CTE.id,CTE.num,CTE.grp,
         BACK_CTE.path,BACK_CTE.cnt, 
         CTE.parent,CTE.CSum 
   from CTE
   JOIN BACK_CTE on CTE.id=BACK_CTE.parent 
              and CTE.Grp=BACK_CTE.Grp
              and BACK_CTE.CSum-BACK_CTE.num=CTE.CSum
) 
select id,NUM,path, cnt as ItemsCount   from BACK_CTE order by cnt,path,Id

perfect! the first row is the expected result! thank you. – armen Jan 09 '14 at 14:47 — armen, Jan 09 '14 at 14:47

Twinkles · Answer 2 · 2014-01-09T13:08:04.633

1

If you restrict your problem to "which two numbers add up to a value", the solution is as follows:

SELECT t1.id, t1.num, t2.id,t2.num
FROM T t1 
INNER JOIN T t2
ON t1.id < t2.id
WHERE t1.num + t2.num  = 150

If you also want the result for three and more numbers you can achieve that by using the above query as a base for recursive SQL. Don't forget to specify a maximum recursion depth!

edited Jan 09 '14 at 13:08

answered Jan 09 '14 at 13:01

Twinkles

1,984
1
17
31

i don't have much knowledge about recursion. I'll read more about recursion to try your approach. – armen Jan 09 '14 at 13:43

score 0 · Answer 3 · answered Jan 09 '14 at 12:49

0

To find the id's of the books that the client is paying, you would need to have a table with your clients, and another one to store the orders of the client, and what products he bought.

Otherwise it would be impossible to know what product the payment refers to.

answered Jan 09 '14 at 12:49

LcSalazar

16,524
3
37
69

of course there is a client id, I've just minimized the problem, so the table contain info for one client only. – armen Jan 09 '14 at 13:37

sql server : select rows who's sum matches a value

3 Answers3

Linked

Related