Hi Dwain,

Thanks for that. I like the way you build tuples and then use them, and I'll see where that takes me. Sorry it's taken so long to reply - I've had a bit of a hectic week.

The comments on your code suggest that you interpreted me correctly, but

unfortunately the code doesn't get all the distinct set of sums mentioned above: it leaves some out. The problem is in this block of code:

SELECT rn, n, TotVal=SUM(TotVal)

FROM

(

-- Split the delimited list (a combination of coin values)

-- and apply a Tally table to get 0 to ccount of each

SELECT rn, Item, d.n, TotVal=Item*d.n

FROM

(

-- Number each unique combination

SELECT *, rn=ROW_NUMBER() OVER (ORDER BY (SELECT NULL))

FROM UniqueCoinCombos

) a

CROSS APPLY DelimitedSplit8K(Tuples, ',') b

JOIN #coinlist c ON b.Item = c.val

CROSS APPLY

(

SELECT n

FROM Tally

WHERE n BETWEEN 0 AND c.ccount

) d

) a

GROUP BY rn, n

The problem is that for each value of n only 1 combination will be considered for that value of n; the combination in which every denomination listed in the tuple and allowed at least that many coins has n coins and every other denomination has none. So any combination in which two coins occur in different nonzero numbers is omitted. For example if the starting point is very simple - up to 1 one cent coin and up to 2 ten cent coins are allowed and nothing else the only combinations that will be noted for the uple 0,1 are

no coins at all (n=0) total 0 cents

one one cent coin and one ten cent coin (n=1) total 11 cents

no one cent coins and two ten cent coins (n=2) total 20 cents

The combination one on cent coin and two ten cent coins, total 21 cents, is not counted because the two coins would be present in different quantities. So the count would be reported as 4 (1,10,11 and 20) but is actually 5 (1,10,11,20 and 21).

I checked this by running an example:

I ran with values(1,1),(2,2),(10,1) in coins to see what would happen, with the code modified display the result of the select above instead of the final result, with each row labelled by the tuple that generated it, because I was sure the error lay there. The tuple 1,2,10 got only 3 rows, with Totval values 0, 13 and 10, so 15, which was possible for this tuple and only for this tuple, was missing. Also the tuple 2,10 got only 0, 12 and 4 so 14 was showing up for neither of the two tuples that could generate it. This meant that the number of distinct sums reported would be 2 less than the actual number of distinct sums possible.

The idea of building tuples and then using a splitter to pull them apart looks promising. I am going to have a look and see if I gets me where I want to be, ie in a position to do early pruning for the case where all the joins are necessary because none of the conditions for alternative algorithms are satisfied without losing the ability to cope with a fairly unlimited variable number of denominations. I think I will have to either invent some rules such as no two denominations may be coprime and no denomination can be more than 500 times the smallest denomination, or have a much smaller limits on number of coins, though.