Solutions for T-SQL Challenge - Combinations | ITPro Today: IT News, How-Tos, Trends, Case Studies, Career Tips, More

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

Comments

Plain text