Solutions for T-SQL Challenge - Combinations

Last week I provided a challenge to return all distinct sums of amounts that
can be produced by combining voucher amounts. You can find the details of
the puzzle here.
Some of the solutions that I got only work with a very small number of
vouchers, and some assumed that the voucher ids were consecutive. I did
not restrict the puzzle to any max number of supported vouchers, and also I
didn’t say that the voucher ids are guaranteed to be consecutive. Perhaps
the following sample data would be better both because it contains more
rows, and the voucher ids are not consecutive:

INSERT INTO dbo.Vouchers(vid, amt) VALUES(289259705, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(729654016, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(846903507, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1732389632, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(2109906632, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1402967178, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1321133695, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1418033096, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(354088652, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(440041219, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1516037031, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(609379976, 100000.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1226959573, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1304128578, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1858455967, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(534179178, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1978894689, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1311299350, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1234941850, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(631714085, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1697467957, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(498685660, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1485686254, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(849438938, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1483766029, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1727642159, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1813918794, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1343915635, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(18249696, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1162905308, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1303053583, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1695736150, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(760721897, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(903396746, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1439784976, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1162671357, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1888131822, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(2013451271, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(250794646, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1081440100, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(2064641957, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(623825308, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(544160166, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(130160010, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(2129982412, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(979954700, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(654933530, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1173116515, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(738057820, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1818452251, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1150454038, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1666678317, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1660997568, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(222879038, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1556217419, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(419472703, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(229336478, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1777246338, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(82421294, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(2040660766, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(383408302, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1659603024, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1236034486, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1321250709, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1956602510, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(2092550549, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1340944086, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1056568305, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1950952112, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(671107320, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1816978600, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1205276281, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(2078693541, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1683827834, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1872994087, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(984288748, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(16594035, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1494056106, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(284392772, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1686306878, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1639170929, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1704823245, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1978188724, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1519096397, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(679880030, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1359009690, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(208551467, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(935471474, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(289245708, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(2101713555, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(228787138, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1048396357, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1555568739, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(964956737, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(2072841200, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1879394273, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1924994802, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(862316104, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(321684953, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1315225953, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(867805658, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1555202725, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1474480234, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1571707830, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1956269486, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1499960398, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1417747632, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1041707679, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(30398160, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(261328400, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(182639968, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(2144083442, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(903365539, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(260770916, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1094215748, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(337990662, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(431253624, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(751241208, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1366814776, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1536354435, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(499538272, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1060644832, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1611494475, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(891109507, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(228711485, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(710522738, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(410493954, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(34433316, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(572035478, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(676014558, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(117033853, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(624682164, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1029242518, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1876301784, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(2044991201, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1913262113, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1892706881, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1825377418, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(676805306, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1272635498, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1568444769, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(2120226547, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1536937928, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1477649144, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(596422822, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(2062527919, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(1407373590, 10.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(21164106, 20.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(238501481, 30.00);INSERT INTO dbo.Vouchers(vid, amt) VALUES(408840862, 30.00);

You can come up with fairly simple solutions if you don’t aim at good
performance. The basic idea is to calculate the sums of all possible
combinations of vouchers without pruning duplicates in the process, and
finally select the distinct sums. For example, the following solution with very
similar versions written by Dieter Noeth and myself:

WITH PowerSet AS(  SELECT amt, vid AS last_vid  FROM dbo.Vouchers  UNION ALL  SELECT P.amt + V.amt, V.vid  FROM PowerSet AS P    JOIN dbo.Vouchers AS V      ON V.vid > P.last_vid)SELECT DISTINCT amtFROM PowerSetORDER BY amt;

The problem with this approach is that it is extremely inefficient—for n
vouchers, there are 2^n possible combinations. So beyond a very small
number of vouchers, the number of combinations can get quite large. For
example, with the 150 vouchers in the new sample data I provided here,
there are 2^150 possible combinations
(1427247692705959881058285969449495136382746624).
The following solutions by Alexey Gasperovich, Zsolt Soczo and Rob
Farely also do not prune duplicates in the process rather only at the end. All
three solutions support only a small number of vouchers, and the solutions
by Zsolt and Rob assume that the voucher ids start with 1 and are
consecutive:

-- Alexey Gasperovichselect distinct SUM(t.amt) as amtfrom master..spt_values as n join (  select POWER ( 2 , row_number() over ( order by vid ) - 1) as ex, amt  from dbo.Vouchers ) as t on t.ex & n.number > 0where n.type = 'p'group by n.numberorder by amt-- Zsolt Soczowith Number(Num)as(select 1 as Numunion allselect Num + 1from Numberwhere Num 
Notice that even though the three solutions might seem similar on the 
surface, Rob’s solution doesn’t require an auxiliary table of numbers 
(potentially, a huge one) like the other two. 
If you do care about performance, you would have to prune duplicates in 
the process. Following are several solutions that do so and run under a 
minute on my laptop with the new sample data I provided here. The fastest 
was provided by Steve Kass, and runs for only 0.2 seconds!

-- Itzik Ben-Gan 1-- 11 secondsCREATE TABLE #Amounts(  amt MONEY NOT NULL PRIMARY KEY,  last_vid INT NOT NULL);INSERT INTO #Amounts(amt, last_vid)  SELECT amt, MIN(vid) as last_vid  FROM dbo.Vouchers  GROUP BY amt;DECLARE @rc AS INT;SET @rc = @@rowcount;WHILE @rc > 0BEGIN  UPDATE U    SET last_vid = D.min_vid  FROM #Amounts AS U    JOIN (SELECT A.amt + V.amt AS amt, MIN(V.vid) AS min_vid          FROM #Amounts AS A            JOIN dbo.Vouchers AS V              ON V.vid > A.last_vid          GROUP BY A.amt + V.amt) AS D      ON U.amt = D.amt AND U.last_vid > D.min_vid;  SET @rc = @@rowcount;  INSERT INTO #Amounts(amt, last_vid)    SELECT A.amt + V.amt, MIN(V.vid)    FROM #Amounts AS A      JOIN dbo.Vouchers AS V        ON V.vid > A.last_vid    GROUP BY A.amt + V.amt    HAVING NOT EXISTS      (SELECT * FROM #Amounts AS A2       WHERE A2.amt = A.amt + V.amt);  SET @rc = @rc + @@rowcount;ENDSELECT amt FROM #Amounts;DROP TABLE #Amounts;GO-- Itzik Ben-Gan 2 (SQL Server 2008)-- 8 secondsCREATE TABLE #Amounts(  amt MONEY NOT NULL PRIMARY KEY,  last_vid INT NOT NULL);INSERT INTO #Amounts(amt, last_vid)  SELECT amt, MIN(vid) as last_vid  FROM dbo.Vouchers  GROUP BY amt;WHILE @@rowcount > 0  WITH SRC AS  (    SELECT A.amt + V.amt AS amt, MIN(V.vid) AS min_vid    FROM #Amounts AS A      JOIN dbo.Vouchers AS V        ON V.vid > A.last_vid    GROUP BY A.amt + V.amt  )  MERGE #Amounts AS TGT  USING SRC    ON SRC.amt = TGT.amt  WHEN MATCHED AND TGT.last_vid > SRC.min_vid THEN    UPDATE SET last_vid = SRC.min_vid  WHEN NOT MATCHED THEN    INSERT(amt, last_vid)      VALUES(SRC.amt, SRC.min_vid);SELECT amt FROM #Amounts;DROP TABLE #Amounts;GO-- Steve Kass-- 0.2 secondsdeclare @Nums table (   n int primary key);insert into @Nums values (0);insert into @Numsselect top 1 with ties   ROW_NUMBER() over (     partition by amt     order by vid   ) as rnfrom Vouchersorder by count(vid) over (   partition by amt) desc;declare @VouchersNumbered table (   k int primary key,   ct int not null,   amt money not null);  insert into @VouchersNumbered  select top (1) with ties    dense_rank() over (      order by amt    ),    count(vid) over (      partition by amt    ),    max(amt) over (      partition by amt    )  from dbo.Vouchers  order by row_number() over (      partition by amt      order by vid    );declare @last int;set @last = (   select max(k)   from @VouchersNumbered);declare @lastUsed int;set @lastUsed = 1;declare @Sums table (   lastUsed int not null,   amt money not null,   primary key(amt,lastUsed));insert into @Sums  select   @last,   cast(n*amt as money)  from @VouchersNumbered as V  join @Nums as N  on N.n  $0   order by amt;go-- Marcello Poletti 1create view vXwith schemabinding asselect amt, count_big(*) cfrom dbo.vouchersgroup by amtgocreate unique clustered index i1 on vX(amt) go -- Marcello Poletti 1a-- 7 secondswith x as(   select *   from vX with(noexpand) ), r as(   select amt, v=amt, n=1, l=1   from x   union all   select x.amt+r.amt, x.amt,     n = 1 + case when x.amt=r.v then r.n else 0 end,     l=l+1   from x     inner join r       on x.amt=r.v and x.c>r.n or x.amt>r.v)select distinct amt from roption(maxrecursion 0)-- Marcello Poletti 1b-- 8 secondscreate function fx (@v money, @n int)returns table as returnselect *, n=@n+1 from vX with(noexpand) where amt=@v and c>@n union all select *, 1 from vX with(noexpand) where amt>@v go with x as(   select *   from vX with(noexpand) ), r as(   select amt, v=amt, n=1, l=1   from x   union all   select x.amt+r.amt, x.amt, x.n, l=l+1   from r     cross apply fx(r.v,r.n) x ), d as(   select distinct amt from r)select amt from doption(maxrecursion 0)godrop function fxdrop view vx-- Marcello Poletti 2-- 3 secondsset nocount ondeclare @a money, @i intdeclare @t table(amt money primary key)set @i=0while 1=1begin  select top 1 @a=amt, @i=vid  from dbo.Vouchers  where vid>@I order by vid  if @@rowcount=0 break  insert into @t    select amt+@a     from (select amt           from @t           union           select 0) v     where amt+@a not in(select amt from @t)endselect * from @tgo

Cheers,
--
BG