# Three-Item Combinations

> Generate all unique 3-item sets with total cost.

Canonical URL: <https://datadriven.io/problems/three_item_combinations>

Domain: SQL · Difficulty: medium · Seniority: L4

## Problem

Given a table of items with names and costs, produce all unique 3-item combinations. For each combo, concatenate the names alphabetically separated by commas, and sum the costs. Return results ranked by total cost descending, then by name ascending.

## Worked solution and explanation

### Why this problem exists in real interviews

Generating combinations tests your understanding of self-joins and the technique for avoiding duplicates in combinatorial results. Interviewers use it to assess whether you can produce unique unordered triplets without repetition.

> **Trick to Solving**
>
> For N-item combinations, use N copies of the table joined with strict inequality constraints.
> 
> 1. Self-join the table three times
> 2. Enforce `a.id < b.id < c.id` to produce unique unordered triplets
> 3. This eliminates both duplicates and permutations

---

### Break down the requirements

#### Step 1: Set up the three-way self-join

Join the table to itself three times: `a`, `b`, `c`. Each alias represents one item.

#### Step 2: Enforce ordering constraints

`WHERE a.item_id < b.item_id AND b.item_id < c.item_id` ensures each combination appears exactly once.

#### Step 3: Select the triplet columns

Return `a.name, b.name, c.name` for each valid combination.

---

### The solution

**Three-way self-join with inequality constraints**

```sql
SELECT
    a.product_name AS item_1,
    b.product_name AS item_2,
    c.product_name AS item_3
FROM products a
JOIN products b ON a.product_id < b.product_id
JOIN products c ON b.product_id < c.product_id
ORDER BY a.product_name, b.product_name, c.product_name
```

> **Cost Analysis**
>
> The number of 3-combinations from N items is `N*(N-1)*(N-2)/6`. For 20K products, that is ~1.3 trillion rows. In practice, this pattern is applied to small filtered subsets. Always filter before combining.

> **Interviewers Watch For**
>
> Interviewers assess whether you immediately recognize the combinatorial explosion risk. Strong candidates ask about the expected input size before writing the query.

> **Common Pitfall**
>
> Omitting the strict inequality and using `!=` instead. `WHERE a.id != b.id AND b.id != c.id AND a.id != c.id` produces all permutations (6x the combinations), not just unique combinations.

---

## Common follow-up questions

- How would you compute the combined price of each triplet? _(Tests adding `a.price + b.price + c.price` to the SELECT.)_
- What if you needed 4-item combinations? _(Tests extending to a 4-way self-join with a.id < b.id < c.id < d.id.)_
- How would you limit this to combinations within the same category? _(Tests adding a category equality condition to the JOIN.)_
- What is the time complexity and how would you optimize for large tables? _(Probes O(N^3) awareness and pre-filtering strategies.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/three_item_combinations)
- [SQL Interview Questions](https://datadriven.io/sql-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.