Last week I provided a challenge
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 < 63)
select distinct SUM(amt)
from Vouchers
cross join Number
where POWER(2, vid-1) = Num & POWER(2, vid-1)
group by Num
-- Rob Farley
with v as
(
select *, power(2,vid-1) as bits
from dbo.Vouchers
),
all_v as
(
select amt, bits from v
union all
select a.amt + v.amt, a.bits + v.bits
from all_v a
join v
on a.bits & v.bits = 0
)
select distinct amt
from all_v
order by amt;
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 <= V.ct
where V.k = 1;
set @lastUsed = 1;
while @lastUsed < @last begin
insert into @Sums
select distinct
@lastUsed + 1,
S.amt + N.n*V.amt
from @VouchersNumbered as V
join @Nums as N
on N.n between 1 and V.ct
cross join @Sums as S
where V.k = @lastUsed + 1
and S.amt + N.n*V.amt not in (
select amt
from @Sums
)
set @lastUsed = @lastUsed + 1;
end;
select distinct amt
from @Sums
where amt > $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
