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

Question

here is table T :-

id  num
-------
 1  50
 2  20
 3  90
 4  40
 5  10
 6  60
 7  30
 8  100
 9  70
10  80

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!

Answer 1

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