Problem

Table: Toppings

+--------------+---------+
| Column Name  | Type    |
+--------------+---------+
| topping_name | varchar |
| cost         | decimal |
+--------------+---------+
topping_name is the primary key for this table.
Each row of this table contains topping name and the cost of the topping.

Write a solution to calculate the total cost of all possible3-topping pizza combinations from a given list of toppings. The total cost of toppings must be rounded to 2 decimal places.

Note:

  • Do not include the pizzas where a topping is repeated. For example, ‘Pepperoni, Pepperoni, Onion Pizza’.
  • Toppings must be listed in alphabetical order. For example, ‘Chicken, Onions, Sausage’. ‘Onion, Sausage, Chicken’ is not acceptable.

Return the result table ordered by total cost in descending order and combination of toppings inascending order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Input: 
Toppings table:
+--------------+------+
| topping_name | cost |
+--------------+------+
| Pepperoni    | 0.50 |
| Sausage      | 0.70 |
| Chicken      | 0.55 |
| Extra Cheese | 0.40 |
+--------------+------+
Output: 
+--------------------------------+------------+
| pizza                          | total_cost | 
+--------------------------------+------------+
| Chicken,Pepperoni,Sausage      | 1.75       |  
| Chicken,Extra Cheese,Sausage   | 1.65       |
| Extra Cheese,Pepperoni,Sausage | 1.60       |
| Chicken,Extra Cheese,Pepperoni | 1.45       | 
+--------------------------------+------------+
Explanation: 
There are only four different combinations possible with the three topings:
- Chicken, Pepperoni, Sausage: Total cost is $1.75 (Chicken $0.55, Pepperoni $0.50, Sausage $0.70).
- Chicken, Extra Cheese, Sausage: Total cost is $1.65 (Chicken $0.55, Extra Cheese $0.40, Sausage $0.70).
- Extra Cheese, Pepperoni, Sausage: Total cost is $1.60 (Extra Cheese $0.40, Pepperoni $0.50, Sausage $0.70).
- Chicken, Extra Cheese, Pepperoni: Total cost is $1.45 (Chicken $0.55, Extra Cheese $0.40, Pepperoni $0.50).
Output table is ordered by the total cost in descending order.

Solution

Intuition

We need to generate all unique 3-topping combinations, sum their costs, and output the results sorted by total cost (descending) and pizza name (ascending). This is a classic self-join/combinatorics problem in SQL, and a combinations problem in pandas.

Approach

  • Use a triple self-join (with alphabetical order enforced) to generate all unique 3-topping combinations.
  • Sum the costs, round to 2 decimals, and concatenate the topping names in alphabetical order.
  • Sort as required.

Code

MySQL
1
2
3
4
5
6
7

SELECT
  CONCAT(t1.topping_name, ',', t2.topping_name, ',', t3.topping_name) AS pizza,
  ROUND(t1.cost + t2.cost + t3.cost, 2) AS total_cost
FROM Toppings t1
JOIN Toppings t2 ON t1.topping_name < t2.topping_name
JOIN Toppings t3 ON t2.topping_name < t3.topping_name
ORDER BY total_cost DESC, pizza ASC;
PostgreSQL
1
2
3
4
5
6
7

SELECT
  t1.topping_name || ',' || t2.topping_name || ',' || t3.topping_name AS pizza,
  ROUND(t1.cost + t2.cost + t3.cost, 2) AS total_cost
FROM Toppings t1
JOIN Toppings t2 ON t1.topping_name < t2.topping_name
JOIN Toppings t3 ON t2.topping_name < t3.topping_name
ORDER BY total_cost DESC, pizza ASC;
Python (pandas)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import pandas as pd
from itertools import combinations

def pizza_toppings_cost_analysis(toppings: pd.DataFrame) -> pd.DataFrame:
    combos = []
    for c in combinations(sorted(toppings['topping_name']), 3):
        costs = toppings.set_index('topping_name').loc[list(c), 'cost']
        pizza = ','.join(c)
        total_cost = round(costs.sum(), 2)
        combos.append((pizza, total_cost))
    df = pd.DataFrame(combos, columns=['pizza', 'total_cost'])
    return df.sort_values(['total_cost', 'pizza'], ascending=[False, True]).reset_index(drop=True)

Complexity

  • ⏰ Time complexity: O(n^3) (where n is the number of toppings; for small n this is acceptable)
  • 🧺 Space complexity: O(n^3) (for storing all combinations)