Here's an example that processes 100 random integers up to 3-tuples with target value of 100. It takes less than 3 seconds to run on my box.

DECLARE @t TABLE (strcol CHAR(4));

DECLARE @ValueOfInterest INT = 100;

INSERT INTO @t (strcol)

--SELECT ' 5' UNION ALL SELECT ' 6' UNION ALL SELECT ' 3'

--UNION ALL SELECT ' 4' UNION ALL SELECT ' 3';

SELECT TOP 100 RIGHT('000' + CAST(ABS(CHECKSUM(NEWID())) % 200 AS VARCHAR(3)), 4)

FROM sys.all_columns;

SET STATISTICS TIME ON;

-- Improved Combinations

WITH UNIQUEnTuples (n, Tuples, ID, CSum) AS (

SELECT DISTINCT 1, CAST(strcol AS VARCHAR(8000)), strcol, CAST(strcol AS INT)

FROM @t

UNION ALL

SELECT 1 + n.n, t.strcol + ',' + n.Tuples, strcol, CSum+t.strcol

FROM UNIQUEnTuples n

CROSS APPLY (

SELECT strcol

FROM @t t

WHERE t.strcol < n.ID) t

WHERE CSum+t.strcol <= @ValueOfInterest

)

SELECT TOP 5 Tuples, SumOfTuples=CSum

FROM UNIQUEnTuples

WHERE n <= 3 AND CSum <= @ValueOfInterest

ORDER BY CSum DESC

OPTION (RECOMPILE);

SET STATISTICS TIME OFF;

Edit: Two notes (afterthoughts):

- I added OPTION(RECOMPILE) because it might help to eliminate parameter sniffing in case you run this many times on tables of different sizes.

- If you need to consider a solution (from your original problem) like 3+3, you need to remove the DISTINCT clause in the anchor leg of the query.