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 amt                              FROM PowerSet                              ORDER 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 Gasperovich                              select distinct SUM(t.amt) as amt                              from 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 > 0                              where n.type = 'p'                              group by n.number                              order by amt                              -- Zsolt Soczo                              with Number(Num)                              as                              (select 1 as Num                              union all                              select Num + 1                              from Number                              where 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 seconds                              CREATE 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 > 0                              BEGIN                                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;                              END                              SELECT amt FROM #Amounts;                              DROP TABLE #Amounts;                              GO                              -- Itzik Ben-Gan 2 (SQL Server 2008)                              -- 8 seconds                              CREATE 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 seconds                              declare @Nums table (                                 n int primary key                              );                              insert into @Nums values (0);                              insert into @Nums                              select top 1 with ties                                 ROW_NUMBER() over (                                   partition by amt                                   order by vid                                 ) as rn                              from Vouchers                              order 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 1                              create view vX                              with schemabinding as                              select amt, count_big(*) c                              from dbo.vouchers                              group by amt                              go                              create unique clustered index i1 on vX(amt)                               go                               -- Marcello Poletti 1a                              -- 7 seconds                              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,                                   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 r                              option(maxrecursion 0)                              -- Marcello Poletti 1b                              -- 8 seconds                              create function fx (@v money, @n int)                              returns table as return                              select *, 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 d                              option(maxrecursion 0)                              go                              drop function fx                              drop view vx                              -- Marcello Poletti 2                              -- 3 seconds                              set nocount on                              declare @a money, @i int                              declare @t table(amt money primary key)                              set @i=0                              while 1=1                              begin                                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)                              end                              select * from @t                              go                                                            Cheers,                              --                              BG                                                             `