Hi Tom,

A generic cte is possible, but I want to show you my WHILE loop first because it can handle the data and my CTE can't!

/* Combinations of coins - generic solution by Mister Magoo */

-- drop our temp tables if they exist

if object_id('tempdb..#values') is not null

drop table #values;

if object_id('tempdb..#coins') is not null

drop table #coins;

if object_id('tempdb..#results') is not null

drop table #results;

-- lets have a table for the coins - denomination and quantity

create table #coins(den smallint primary key not null,number int not null);

-- and some test data

insert #coins(den,number)

values(1,3),(2,2),(5,0),(10,3),(50,1); -- should come up with 63 values

/* some more test */

--values(1,1),(2,5000),(5,1),(10,2),(20,1),(50,7),(100,402),(200,35); -- should come up with 57596 values

--values(1,1),(2,5000),(5,1),(10,2),(20,1),(50,7),(100,402),(200,35),(500,99); -- should come up with 107096 values

-- let's build a tally cte

;with

E1(N) AS (

SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL

SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL

SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1

), --10E+1 or 10 rows

E2(N) AS (SELECT 1 FROM E1 a, E1 b), --10E+2 or 100 rows

E4(N) AS (SELECT 1 FROM E2 a, E2 b) --10E+4 or 10,000 rows max

/* you can add more elements to the cte to handle larger numbers of coins per denomination if required */

-- now generate all the possible values for each coin denomination

select den,den*n as value

into #values

from #coins coins

cross apply(

select 0

union all

select top (coins.number) row_number() over (order by (select null)) from e4

) ctetally(n);

-- index the list so we can get each denomination's values quickly

create clustered index ix_vals_ci on #values(den);

-- create somewhere to put the results

-- NOTE: the use of identity on "den" is to remove the need for an index

-- we can tell what we last processed by checking scope_identity()

create table #results(den int identity(1,1) not null , value int not null);

-- allow direct insertes of identity values

set identity_insert #results on;

-- add the first set of results for the first coin denomination

insert #results(den,value)

select den,value

from #values

where den = (Select min(den) from #values);

-- now a single statement while loop to insert the rest of the results

-- this works out as X inserts of sets of data where X = the number of coin denominations in the #coins table

-- this is the same logic as a recursive cte, but many times faster

while @@rowcount>0

insert #results(den,value)

-- use of distinct saves us processing duplicates as we go along

select distinct vals.den,base.value + vals.value

from

( -- let's get the last set of data we inserted from the #results table by using scope_identity() to identify them

select distinct value

from #results res

where res.den = scope_identity()

) base

cross join

( -- and cross join that with all the possible values of the next coin in the #coins table

select den,value

from #values vals

where vals.den = (

select top 1 coins.den

from #coins coins

where coins.den> scope_identity()

order by coins.den)

) vals;

-- finally the results, excluding zero

select distinct value

from #results

where value>0

order by value;

The rubbish CTE is here:

;with

coins(den,number) as

(

select den,number from (values(1,3),(2,2),(5,0),(10,3),(50,1))a(den,number)

),

E1(N) AS (

SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL

SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL

SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1

), --10E+1 or 10 rows

E2(N) AS (SELECT 1 FROM E1 a, E1 b), --10E+2 or 100 rows

E4(N) AS (SELECT 1 FROM E2 a, E2 b) --10E+4 or 10,000 rows max

, vals(den,value) as

(

select den,den*n

from coins

cross apply(

select 0

union all

select top (coins.number) row_number() over (order by (select null)) from e4

) ctetally(n)

), combinations as

(

select den,value

from vals

where den=(select min(den) from coins)

union all

select vals.den, vals.value + combi.value

from combinations as combi

cross apply ( select den,value

from (

select den,value,rank() over(order by den) as rnk

from vals

where vals.den>combi.den

) a

where a.rnk = 1

) vals

)

select distinct value

from combinations

where value>0