# Thread: SQL Challenge: Numeric Combinations

1. www.gvee.co.uk
Join Date
Jan 2007
Location
UK
Posts
11,445

## Unanswered: SQL Challenge: Numeric Combinations

I've been working with some interesting data puzzles recently and it got me thinking of some little challenges to try and solve in T-SQL.

So here's one:
Code:
```DECLARE @x table (
id    int
, price money
)

INSERT INTO @x (id, price)
VALUES (1, 1.0)
, (2, 1.0)
, (3, 1.0)
, (4, 1.5)
, (5, 1.5)
, (6, 2.0)
, (7, 2.5)
, (8, 2.5)
, (9, 3.5)

DECLARE @target money = 3.0

/*
Aim: find all combinations of items that when
added together equal the target amount.

Expected results if @target = 2.5:
1, 4
1, 5
2, 4
2, 5
3, 4
3, 5
7
8

Expected results if @target = 3.0:
1, 2, 3
1, 6
2, 6
3, 6
4, 5

Expected results if @target = 3.5:
1, 2, 4
1, 3, 4
2, 3, 4
1, 2, 5
1, 3, 5
2, 3, 5
4, 6
5, 6
1, 7
1, 8
2, 7
2, 8
3, 7
3, 8
9
*/```
I'm stumped on how to approach this one, any ideas?

Good luck!

2. Registered User
Join Date
Jan 2013
Posts
358

## NP-complete knapsack problem

This is called a knapsack problem and it is known to be NP-complete. You are dead before you start. A procedural program with a greedy algorithm that halts on the first result actually does pretty good.

Operation Research

The FORTRAN is awful and unstructured, but usable with lots of effort.

My trick for small sets of (n) items in SQL was a table of {0, 1} in (n) and use a cross join to generate all possible combinations and their total. The other trick for larger values of (n) is to do (n-k) and discard the subset that overflowed. Take the candidates and add another column for the (n-k-1) case, repeat until you hit (n-k-k) columns. Brute force, plain and simple.

3. www.gvee.co.uk
Join Date
Jan 2007
Location
UK
Posts
11,445
Thanks Joe, I will give that a read.

I'm kind of glad that it's not just me that can't solve it - I was starting to doubt my ninja-SQL skills!

It is a reasonably trivial problem I had to keep working out in my head and on paper on some data analysis stuff over the last week and just assumed there would be a much cleverer way that I hadn't thought of

4. World Class Flame Warrior
Join Date
Jun 2003
Location
Ohio
Posts
12,595
...and if Price can be negative, the problem gets even worse.

5. Registered User
Join Date
Nov 2003
Posts
2,988
I do have a solution using a recursive query:

Table setup:
Code:
```create table x
(
id    int not null primary key,
price numeric(12,4) not null
);

INSERT INTO x
(id, price)
VALUES
(1, 1.0),
(2, 1.0),
(3, 1.0),
(4, 1.5),
(5, 1.5),
(6, 2.0),
(7, 2.5),
(8, 2.5),
(9, 3.5);```
The actual query:
Code:
```with calc as (
select id as id,
cast(id as varchar(max)) as id_list,
cast(price as numeric(14,2)) as price
from x
where price <= 2

union all

select c.id,
p.id_list+','+ cast(c.id as varchar(max)),
cast((c.price + p.price) as numeric(14,2))
from x as c
join calc as p on p.id < c.id
where c.price + p.price <= 2
)
select *
from calc
where price = 2
order by id_list```
The base query calculates more combinations than are actually needed.
Limiting the values inside the CTE to less than the max. amount is an attempt to make it a bit more efficient.

I don't expect this to scale very well though.

Here is a SQLFiddle to play around with: http://sqlfiddle.com/#!6/77530/11
Last edited by shammat; 04-09-13 at 14:21. Reason: Replaced Postgres only solution (using arrays) with SQL Server solution using a varchar

6. www.gvee.co.uk
Join Date
Jan 2007
Location
UK
Posts
11,445
First off... sqlfiddle: GENUIS!
I have used jsfiddle before but never knew an SQL equivalent existed! Bookmarked and signed up 8)

Secondly.... that looks lovely!
Very similar to something I tried earlier but I didn't wrap my head around the join criteria (and the following WHERE clause).

Will give it a proper looksie tomorrow

7. World Class Flame Warrior
Join Date
Jun 2003
Location
Ohio
Posts
12,595
Originally Posted by shammat
Limiting the values inside the CTE to less than the max. amount is an attempt to make it a bit more efficient.
...which is where negative prices would really gum things up.

8. www.gvee.co.uk
Join Date
Jan 2007
Location
UK
Posts
11,445
Luckily, for my real-world requirements, there is no negative (or zero) pricing

Because it's not actually prices I'm dealing with, but it just seemed like an easier to explain scenario

9. World Class Flame Warrior
Join Date
Jun 2003
Location
Ohio
Posts
12,595
I thought this was just a "puzzle" George.
Wait, this isn't a homework assignment is it?

10. Registered User
Join Date
Jan 2013
Posts
358

## Actually, I did a puzzle like this ..

The Best Sub-Array Problem

Use a one-dimensional array, slots[1:n], and we want to find a sub-array, slots [a:b] , where (1 <= a <= b <= n) and SUM (slots [a:b]) is a maximum.

If all the slots are positive or zero, then the sum of the whole array is the answer. Problem solved! But negative numbers make problems:
1
1
-5
1
1

The total for all five slots is -1, so that does not work. The best sub-arrays are slots[1:2] and slots [4:5] , so a simple total summation will not work.”

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•