Sean Lange (7/31/2013)

---

dwain.c (7/30/2013)

---

I love SQL bin-packing problems! Hate to disagree with you Sean but they don't need to be overly complicated.

Before I suggest a solution, shouldn't the answer be 4, 6 (=10?)

Here's one solution that might start to get a little slow if you have:

- lot's of integers in your table AND

- you want to consider solutions that sum more than 3, 4 or 5 of those.

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

DECLARE @ValueOfInterest INT = 10;

INSERT INTO @t (strcol)

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

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

-- 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+CAST(t.strcol AS INT)

FROM UNIQUEnTuples n

CROSS APPLY (

SELECT strcol

FROM @t t

WHERE t.strcol < n.ID) t

)

SELECT TOP 1 Tuples, SumOfTuples=CSum

FROM UNIQUEnTuples

WHERE n <= 2 AND CSum <= @ValueOfInterest

ORDER BY CSum DESC;

This is actually a slightly improved version of some code I submitted a couple of years back: Generating n-Tuples with SQL[/url]. The improved version appears towards the end of the discussion thread.

Note that the WHERE clause can be adjusted to account for the number of integers you want to sum and/or whether you allow the value to be within a plus or minus range, for example:

WHERE n <= 3 AND CSum BETWEEN @ValueOfInterest - 1 AND @ValueOfInterest + 1

Would give you up to 3 summed integers where the range is plus or minus 1 from your value of interest. Of course, you may want to select the TOP 5 in such a case and then later decide to narrow it down.

Edit: Note also that if the number of integers to sum is unbounded, meaning you don't care how many sum to meet your target, you should put a CSUM <= @ValueOfInterest WHERE clause in the recursive leg of the rCTE so that on the result that exceeds your target, all further combinations are avoided.

Dwain this is pretty cool but it doesn't provide the results the OP was looking for. This only returns the one combination that most closely meets the @ValueOfInterest. The OP was looking to have all the values put into groups. The OP stated they wanted back 5,4 and 6,3. Now I agree that doesn't seem like the most logical thing and the second value of 3 went missing. I would think that 6,4 : 5,3 : 3 would be the best fit. I can't some up with a way to make your awesome example return the best fit of all the values.