LeetCode 638: Shopping Offers

Problem Restatement

We are given item prices, special bundle offers, and the exact number of each item we need to buy.

Each item i has an individual price:

price[i]

Each special offer contains quantities of items plus a final bundle price:

special[j] = [count_item_0, count_item_1, ..., offer_price]

We can use each special offer any number of times.

The goal is to pay the minimum total cost while buying exactly the items in needs.

We are not allowed to buy more than needed, even if an offer is cheaper. The official constraints have at most 6 item types, at most 100 offers, and each needs[i] is at most 10.

Input and Output

Example function shape:

def shoppingOffers(
    price: list[int],
    special: list[list[int]],
    needs: list[int],
) -> int:
    ...

Examples

Example 1:

price = [2, 5]
special = [[3, 0, 5], [1, 2, 10]]
needs = [3, 2]

Item 0 costs 2.

Item 1 costs 5.

The offers are:

Without offers:

3 * 2 + 2 * 5 = 16

Using the second offer gives:

1 item0 + 2 item1 for 10

Then we still need two more of item 0:

2 * 2 = 4

Total:

10 + 4 = 14

Using the first offer plus buying item 1 individually gives:

5 + 2 * 5 = 15

So the answer is:

14

Example 2:

price = [2, 3, 4]
special = [[1, 1, 0, 4], [2, 2, 1, 9]]
needs = [1, 2, 1]

The answer is:

11

Use the first offer once, then buy the remaining one item 1 and one item 2 individually. The second offer is not allowed because it would buy more item 0 than needed.

First Thought: Try All Offer Combinations

A direct approach is to try all possible counts for each special offer.

For example, use offer 0 zero times, one time, two times, and so on.

This becomes messy because offers can overlap, and each offer can be reused many times.

A better view is:

At any point, what items do we still need?

That remaining need vector fully describes the state.

Key Insight

Let:

dfs(current_needs)

mean:

the minimum cost needed to satisfy current_needs

For any state, we always have one simple option:

buy everything individually

Then we try every special offer that does not exceed the current needs.

If an offer is valid, we apply it, reduce the remaining needs, and solve the smaller subproblem recursively.

Because many different offer orders can lead to the same remaining needs, we memoize each state.

Algorithm

1. Convert needs into a tuple so it can be used as a memoization key.
2. Define dfs(state).
3. Inside dfs, compute the baseline cost by buying all remaining items individually.
4. For each offer:
   1. Check whether the offer quantities are not greater than state.
   2. If valid, subtract the offer quantities from state.
   3. Recursively compute the cost of the remaining state.
   4. Minimize the answer.
5. Return dfs(tuple(needs)).

Implementation

from functools import cache

class Solution:
    def shoppingOffers(
        self,
        price: list[int],
        special: list[list[int]],
        needs: list[int],
    ) -> int:
        n = len(price)

        @cache
        def dfs(state: tuple[int, ...]) -> int:
            best = sum(state[i] * price[i] for i in range(n))

            for offer in special:
                next_state = []
                valid = True

                for i in range(n):
                    if offer[i] > state[i]:
                        valid = False
                        break

                    next_state.append(state[i] - offer[i])

                if valid:
                    best = min(best, offer[-1] + dfs(tuple(next_state)))

            return best

        return dfs(tuple(needs))

Code Explanation

The number of item types is:

n = len(price)

We use @cache so repeated states are solved once:

@cache
def dfs(state: tuple[int, ...]) -> int:

The baseline cost is buying all remaining items one by one:

best = sum(state[i] * price[i] for i in range(n))

This is always valid, so it is a safe initial answer.

Then we test each special offer:

for offer in special:

An offer is valid only if it does not exceed the current need for any item:

if offer[i] > state[i]:
    valid = False
    break

If valid, the next state is:

state[i] - offer[i]

Then the cost of using this offer is:

offer[-1] + dfs(tuple(next_state))

We keep the minimum.

Correctness

For any remaining need state, buying all items individually is a valid way to finish. Therefore, dfs(state) always starts with a valid upper bound.

Now consider an optimal solution for state.

If it uses no special offer first, then its cost is exactly the individual purchase cost, which is included in the baseline.

If it uses some special offer first, that offer must not exceed the current needs. The algorithm checks every offer and allows exactly those that are valid. After applying such an offer, the remaining problem is next_state. By definition, dfs(next_state) gives the minimum cost to finish from there.

Therefore, for every possible first step of an optimal solution, the algorithm considers the same first step and then solves the rest optimally.

Memoization does not change the result. It only reuses previously computed values for the same state.

Thus dfs(tuple(needs)) returns the minimum cost to buy exactly the required items.

Complexity

Let:

n = number of item types
s = number of special offers
m = maximum need per item

There are at most:

(m + 1)^n

possible need states.

For each state, we scan all offers and check up to n item counts.

This is acceptable because n is at most 6 and each need is at most 10.

Optional Optimization: Filter Useless Offers

Some offers cost the same or more than buying their items individually.

Such offers are never helpful.

We can remove them before running DFS.

from functools import cache

class Solution:
    def shoppingOffers(
        self,
        price: list[int],
        special: list[list[int]],
        needs: list[int],
    ) -> int:
        n = len(price)

        useful = []
        for offer in special:
            normal_cost = sum(offer[i] * price[i] for i in range(n))
            if offer[-1] < normal_cost:
                useful.append(offer)

        @cache
        def dfs(state: tuple[int, ...]) -> int:
            best = sum(state[i] * price[i] for i in range(n))

            for offer in useful:
                next_state = []
                valid = True

                for i in range(n):
                    if offer[i] > state[i]:
                        valid = False
                        break
                    next_state.append(state[i] - offer[i])

                if valid:
                    best = min(best, offer[-1] + dfs(tuple(next_state)))

            return best

        return dfs(tuple(needs))

This does not change correctness, because an offer that is not cheaper than individual buying can be replaced by individual purchases.

Testing

def run_tests():
    s = Solution()

    assert s.shoppingOffers(
        [2, 5],
        [[3, 0, 5], [1, 2, 10]],
        [3, 2],
    ) == 14

    assert s.shoppingOffers(
        [2, 3, 4],
        [[1, 1, 0, 4], [2, 2, 1, 9]],
        [1, 2, 1],
    ) == 11

    assert s.shoppingOffers(
        [2],
        [[1, 1]],
        [3],
    ) == 3

    assert s.shoppingOffers(
        [9, 9],
        [[1, 1, 30]],
        [1, 1],
    ) == 18

    assert s.shoppingOffers(
        [3, 4],
        [[1, 1, 5], [2, 2, 9]],
        [2, 2],
    ) == 9

    print("all tests passed")

run_tests()

Test meaning: