This new algorithm is about finding all possible sums and how many combinations you have of each sum.
Have fun!
DECLARE @Data TABLE
(
faceValue MONEY,
maxItems INT,
permCount INT
)
INSERT @Data
(
faceValue,
maxItems
)
SELECT faceValue,
1 + COUNT(*)
FROM (
SELECT 899 AS faceValue UNION ALL
SELECT 100 UNION ALL
SELECT 95 UNION ALL
SELECT 50 UNION ALL
SELECT 55 UNION ALL
SELECT 40 UNION ALL
SELECT 5 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 50 UNION ALL
SELECT 250 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 90 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 50 UNION ALL
SELECT 350 UNION ALL
SELECT 450 UNION ALL
SELECT 450 UNION ALL
SELECT 100 UNION ALL
SELECT 100 UNION ALL
SELECT 50 UNION ALL
SELECT 50 UNION ALL
SELECT 50 UNION ALL
SELECT 1 UNION ALL
SELECT 10 UNION ALL
SELECT 1
) AS d
GROUP BY faceValue
DECLARE @comb INT
UPDATE @Data
SET @comb = permCount = maxItems * COALESCE(@comb, 1)
SELECT theSum,
COUNT(*) AS theCount
FROM (
SELECT SUM(d.faceValue *((v.number * d.maxItems / d.permCount) % d.maxItems)) AS theSum
FROM @Data AS d
INNER JOIN TallyNumbers AS v ON v.number <= @comb
GROUP BY v.number
HAVING SUM(d.faceValue *((v.number * d.maxItems / d.permCount) % d.maxItems)) > 0
) AS d
GROUP BY theSum
ORDER BY COUNT(*) DESC,
theSum
Now you can see for any possible sum how many combination you have to get that sum.
With the sample data provided above, you can see that you can get the sum of 2651 rupees in 966 different ways, but you can only get the sum of 1019 rupees in one way.