Select every possible combination below a certain sum?

Question

I have a table called Item which has an ID, a Name and a Price. Is it possible using SQL select statements to get every possible, but distinct combination of items below a specific price?

For example, assume this table:

ID  Name  Price     
--  ----  -----
1   A     1         
2   B     2         
3   C     3         
4   D     4         
5   E     5

The query, taken the limit is for example 10, shall only return A, B, C, D, but not A, B, D, C additionally.

Is something like this even possible? Please excuse this probably stupid question, but I'm learning SQL for a year now, but our teacher hasn't even explained what SQL means. My entire knowledge is from books, so I'm not sure if this is a suitable question or not.

See http://stackoverflow.com/questions/1899736/getting-all-possible-combinations-which-obey-certain-condition-with-ms-sql for inspiration. — GSerg, Jan 22 '12 at 02:52

score 4 · Answer 1 · edited May 23 '17 at 12:06

Well, since no inspiration was generated by Getting all possible combinations which obey certain condition with MS SQL, here's an adaptation of the code found there ;)

declare @data table (id int not null primary key, name varchar(40) not null, price money not null);
insert into @data (id, name, price) values (1, 'A', 1), (2, 'B', 2), (3, 'C', 3), (4, 'D', 4), (5, 'E', 5);

-- Replace @data with actual table name and delete the above

with
anchor as (
  select id, name, price
  from @data
),
cte as (
  select
    id as max_id,
    price,
    '|' + cast(id as varchar(max)) + '|' as level 
  from anchor

  union all

  select
    a.id as max_id,
    c.price + a.price,
    c.level + '|' + cast(a.id as varchar(max)) + '|' as level
  from
    cte c
    inner join anchor a on a.id > c.max_id and c.level not like '%|' + cast(a.id as varchar(max)) + '|%'
)
select level
from cte
where price <= 10
;

score 1 · Accepted Answer · answered Jan 22 '12 at 02:56

It's a good question, but as far as I know it's not possible with a set-based approach. It might be possible with some sort of CTE-based recursion, but if so, I can't think of how. It could be done with cursors, but not directly with "SQL select statements" (which I interpret to mean a set-based approach).

If you wanted to find all combinations of exactly two numbers that were less then x, you could cross join the table to itself (eliminating rows where the ID was the same) and sum the two prices, excluding sums that were less than x.

Thank you. I'm not really looking for solution with like 50 lines. Either a plain simple answer or a not-possible was enough. Thank you. — MechMK1, Jan 22 '12 at 02:59

score 0 · Answer 3 · answered Jan 22 '12 at 04:33

If you want combinations of 2 items, it is simple, just join the table with itself with no conditions (so you do the cartesian product) and then sum the price of the items in both tables (you can exclude the same item twice, if that is what you need).

IT is not possible to generalize for N items in SQL by definition since it is not possible in relational algebra. You would need a query with N lines with N being the number of records, so you would need to know a max number of records in advance.

Also, the combinatorial of N elements (if that is what you need) is O(N!) so it grows really fast in both size and possibilities, so if you have too many elements and a price large enough you would soon face the limits of any possible computer.

Select every possible combination below a certain sum?

3 Answers3