Given a table of numbers, can I get all the rows which add up to less than or equal to a number?

Say I have a table with an incrementing id column and a random positive non zero number.

id	rand
1	12
2	5
3	99
4	87

Write a query to return the rows which add up to a given number.

A couple rules:

1. Rows must be “consumed” in order, even if a later row makes it a a perfect match. For example, querying for 104 would be a perfect match for rows 1, 2, and 4 but rows 1-3 would still be returned.

2. You can use a row partially if there is more available than is necessary to add up to whatever is leftover on the number E.g. rows 1, 2, and 3 would be returned if your max number is 50 because 12 + 5 + 33 equals 50 and 90 is a partial result.

3. If there are not enough rows to satisfy the amount, then return ALL the rows. E.g. in the above example a query for 1,000 would return rows 1-4. In other words, the sum of the rows should be less than or equal to the queried number.

It’s possible for the answer to be “no this is not possible with SQL alone” and that’s fine but I was just curious. This would be a trivial problem with a programming language but I was wondering what SQL provides out of the box to do something as a thought experiment and learning exercise.

Answer

You didn’t mention which RDBMS, but assuming SQL Server:

DROP TABLE #t;

CREATE TABLE #t (id int, rand int);

INSERT INTO #t (id,rand)
VALUES (1,12),(2,5),(3,99),(4,87);

DECLARE @target int = 104;

WITH dat
AS
(
SELECT id, rand, SUM(rand) OVER (ORDER BY id) as runsum
FROM #t
),
dat2
as
(
SELECT id, rand
, runsum
, COALESCE(LAG(runsum,1) OVER (ORDER BY id),0) as prev_runsum
from dat
)
SELECT id, rand
FROM dat2
WHERE @target >= runsum
OR @target BETWEEN prev_runsum AND runsum;