• Questions
• # How to do a combination to sum to find all the options up to a certain value

Thanks for the question, Juan Carlos.

Asked: August 10, 2016 - 9:33 pm UTC

Last updated: November 15, 2022 - 11:25 am UTC

Version: 12.1.0.1

Viewed 1000+ times

Hello TomConChris

I can have up to 7 (in reality 50) values, and I must sum all the combination and choose all the combination that get an amount
In example All the combinations with the numbers to get a pizza of 5 kg.
option 1 5Kg,
Option 2 3Kg
Option 3 2Kg
Option 4 4Kg
In the previous example I had tow combionatios (option1 5=5) (options2 and option3 2+3=5) both givesme 5.

In the following example I have a way to get all the combinations, in the previous case (option2 +option3=5), but I can't find the option1=5, because all the combinations returns a value, and I need always they include the option, I had done a several test and I couldn't then I thought why to do it, if TomConChris can :)

WITH COMBINACION AS
( SELECT 1 C, 1 Q
FROM DUAL
UNION ALL
SELECT 2 C, 2 Q
FROM DUAL)
SELECT T1.C C1,T2.C C2,T3.C C3,T4.C C4,T5.C C5,T6.C C6,T7.C C7
FROM COMBINACION T1
LEFT OUTER JOIN COMBINACION T2 ON (T2.C NOT IN (T1.C) )
LEFT OUTER JOIN COMBINACION T3 ON (T3.C NOT IN (T1.C,T2.C) )
LEFT OUTER JOIN COMBINACION T4 ON (T4.C NOT IN (T1.C,T2.C,T3.C) )
LEFT OUTER JOIN COMBINACION T5 ON (T5.C NOT IN (T1.C,T2.C,T3.C,T4.C) )
LEFT OUTER JOIN COMBINACION T6 ON (T6.C NOT IN (T1.C,T2.C,T3.C,T4.C,T5.C) )
LEFT OUTER JOIN COMBINACION T7 ON (T7.C NOT IN (T1.C,T2.C,T3.C,T4.C,T5.C,T6.C) );

This resturns
1 2
2 1

I need it inclues all the times a 0 in all the combinations, to get the situations when only one is enough (in reality it has 50 elements)

1 0
1 2
2 0
2 1

if it where three elements
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

I would need

1 0 0
1 2 0
1 2 3
0 2 0
etc.

I tried things like LEFT OUTER JOIN COMBINACION T2 ON (T2.C NOT IN (T1.C) OR T2.C=0) , but I think I'm misunderstanding the working of the LEFT OUTER JOIN, because I never used, truely.

Thank you :) in advance, hope you can solve it :)

## and Chris said...

Eeek! Joining like that limits the number of things you can compare to the number of joins. And it's terrible for performance as your tables have more rows.

There is another way. Recursive SQL.

This will maintain two things

- The total weight so far
- A list of the pizza toppings you've already checked

Obviously we need the weight, because that's what we're measuring. The list is to prevent us checking the same row twice.

So we want to start with all the rows in the table. You could exclude those <= 5kg at this point if necessary. Wrap the topping with hashes. This ensures 1 is not confused with 11, 21, etc. (#1# <> #11#, but 1# is part of 11#, 21# and so on).

```select topping, '#' || topping || '#', weight tot_wt from t
```

To build the recursive case, we now:

Join the original table where:

- The topping is not in the list already considered
- The total weight + new weight <= 5
- The current topping number is greater than those considered. This is to prevent double counting 2,3 and 3,2

For each row that passes these checks, append its topping to the list of those already processed and increment the total weight:

```select t.topping, toppings || t.topping || '#', tot_wt + weight tot_wt
from   tots
join   t
on     instr(toppings, '#' || t.topping || '#') = 0
and    tot_wt + weight <= 5
and    tots.topping < t.topping
```

Put it all together and you have:

```create table t (
topping int,
weight  int
);

insert into t values ( 1, 5 );
insert into t values ( 2, 3 );
insert into t values ( 3, 2 );
insert into t values ( 4, 4 );

with tots (topping, toppings, tot_wt) as (
select topping, '#' || topping || '#', weight tot_wt from t
union all
select t.topping, toppings || t.topping || '#', tot_wt + weight tot_wt
from   tots
join   t
on     instr(toppings, '#' || t.topping || '#') = 0
and    tot_wt + weight <= 5
and    tots.topping < t.topping
)
select toppings, tot_wt from tots;

TOPPINGS  TOT_WT
#1#       5
#2#       3
#3#       2
#4#       4
#2#3#     5
```

This gets you all the combinations that weight up to 5kg. Add a 1kg option and it still works:

```insert into t values ( 5, 1 );

with tots (topping, toppings, tot_wt) as (
select topping, '#' || topping || '#', weight tot_wt from t
union all
select t.topping, toppings || t.topping || '#', tot_wt + weight tot_wt
from   tots
join   t
on     instr(toppings, '#' || t.topping || '#') = 0
and    tot_wt + weight <= 5
and    tots.topping < t.topping
)
select toppings, tot_wt from tots;

#1#       5
#2#       3
#3#       2
#4#       4
#5#       1
#2#3#     5
#2#5#     4
#3#5#     3
#4#5#     5
```

If you want just those that are exactly 5kg, add this to the final where clause!

## Rating

(3 ratings)

Is this answer out of date? If it is, please let us know via a Comment

### Thank you :)

Reyes, August 11, 2016 - 3:44 pm UTC

August 12, 2016 - 3:19 am UTC

vivek, November 15, 2022 - 8:29 am UTC

Hi Team,

I had a similar requirement and made use of the query with addition where clause which can give me the combinations that are exact match.

But after adding the where clause, query running for long period of time.

Thanks,
Vivek K

November 15, 2022 - 11:25 am UTC

What is your query? What is it's execution plan?