Shopping Offers: Backtracking with Memoization

You walk into a store with a shopping list. Each item has a fixed price, but the store also has bundle deals that let you buy groups of items at a discount. You want to buy exactly what you need for the lowest possible cost. Should you mix and match bundles, use just one, or skip them entirely and pay full price?

This is LeetCode 638: Shopping Offers, and it captures a surprisingly common optimization pattern. You are given a list of item prices, a set of special offers (bundles), and the exact quantities you need. Your goal is to find the minimum cost to fulfill your shopping list, where you can use each offer as many times as you like but cannot buy more of any item than you need.

Why this problem matters

Shopping Offers blends two fundamental techniques: backtracking to explore all valid combinations of offers, and memoization to avoid recomputing the cost for the same remaining needs. If you have worked through Combination Sum or Coin Change, you already know the building blocks. This problem combines them in a practical setting.

The key difficulty is that the "state" is not a single number (like a remaining amount in Coin Change) but a tuple of remaining quantities. That shift from scalar state to multi-dimensional state is something you will encounter in many DP and backtracking problems. Shopping Offers is a clean, approachable example of it.

It also teaches you to filter out bad offers early. An offer that costs more than buying its items individually is never worth taking. Pruning these before you start searching keeps the recursion tree small.

The approach

The algorithm uses depth-first search with memoization:

1. For each state (represented as a tuple of remaining needs), compute the cost of buying everything at individual prices. This is your baseline.
2. Try applying each special offer. An offer is valid only if every item quantity in the offer is at most the remaining need for that item. You also skip offers that cost more than buying those items individually.
3. For each valid offer, subtract the offer quantities from your needs, add the offer price, and recurse on the reduced needs.
4. Return the minimum cost across all choices (individual purchase vs. each valid offer).
5. Memoize on the needs tuple so you never solve the same sub-problem twice.

The needs tuple is the state. Because each item quantity is small (at most 6 per the constraints), the total number of distinct states is bounded and memoization is effective.

def shoppingOffers(price, special, needs):
    memo = {}

    def dfs(needs):
        needs_key = tuple(needs)
        if needs_key in memo:
            return memo[needs_key]

        cost = sum(needs[i] * price[i] for i in range(len(price)))

        for offer in special:
            new_needs = []
            valid = True
            for i in range(len(price)):
                if offer[i] > needs[i]:
                    valid = False
                    break
                new_needs.append(needs[i] - offer[i])

            if valid:
                cost = min(cost, offer[-1] + dfs(new_needs))

        memo[needs_key] = cost
        return cost

    return dfs(needs)

Step-by-step walkthrough

Let's trace through the algorithm with price = [2, 5], special = [[3, 0, 5], [1, 2, 10]], and needs = [3, 2]. Item A costs $2 and Item B costs $5. Offer 1 gives you 3 of A for $5. Offer 2 gives you 1 of A and 2 of B for $10.

The recursion explores every valid sequence of offers and always falls back to individual pricing for whatever remains. Memoization ensures that if two different sequences of offers lead to the same remaining needs, the cost is only computed once.

Complexity analysis

Here n is the number of items, k is the number of special offers, and m is the maximum quantity needed for any item (at most 6). The state space has at most m^n distinct needs tuples. For each state, we try all k offers and do O(n) work to validate each one. The constraints keep n and m small (both at most 6), so this runs well within time limits.

The space is O(m^n) for the memoization table, plus O(n * m) for the recursion stack depth.

Edge cases to watch for

• No special offers: the answer is simply the sum of needs[i] * price[i] for all items. The algorithm handles this naturally since no offer passes the validity check.
• An offer that exceeds a need: for example, an offer gives 5 of Item A but you only need 2. This offer is invalid for the current state and must be skipped. You cannot buy more than you need.
• An offer more expensive than individual prices: if Offer 1 gives [1, 1] for $10 but buying 1 of A ($2) and 1 of B ($5) costs $7, the offer is never worth taking. You can optionally pre-filter these, but the algorithm will naturally avoid them since the individual cost baseline will always be cheaper.
• All needs are zero: the cost is 0. This is the base case that the recursion bottoms out on (the sum of 0 * price[i] = 0).
• Using the same offer multiple times: this is allowed and the recursion handles it by trying each offer again at every level. If Offer 1 can be applied twice in a row, the DFS will explore that path.

The building blocks

This problem sits at the intersection of two patterns you have seen before.

Backtracking with pruning

The search structure is the same as Combination Sum. At each step, you have a set of choices (the offers). You try each valid choice, recurse on the reduced state, and implicitly backtrack when the recursive call returns. The "pruning" here is skipping offers that exceed any item's remaining need.

Memoization on tuple state

The memoization pattern is similar to Coin Change, but the state is a tuple instead of a single integer. In Coin Change, the memo key is the remaining amount. Here, the memo key is the tuple of remaining item quantities. This multi-dimensional memoization pattern appears in many problems where the state has more than one axis.

The combination of these two building blocks, recursive exploration of choices with memoized states, is a pattern you will use over and over. Target Sum is another example where you explore branching choices (add or subtract) and memoize on a composite state (index plus running sum).

From understanding to recall

You can follow the logic: try each offer, recurse on reduced needs, memoize the tuple. But in an interview, will you remember to use the needs tuple as the memo key? Will you remember to check that each offer quantity does not exceed the remaining need? Will you remember the baseline cost calculation?

These details are easy to read but hard to reproduce under pressure. Spaced repetition bridges that gap. You practice writing the DFS with memoization from scratch, and after a few reps the pattern becomes automatic. When you see a problem with multi-dimensional state and repeated subproblems, the structure clicks into place without hesitation.

The backtracking-plus-memoization pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Combination Sum - The core backtracking pattern of choosing from a set of options with reuse allowed. Shopping Offers adds memoization on top of the same recursive structure.
• Coin Change - Classic memoization on a scalar state. Shopping Offers extends this to a tuple state, but the memoization logic is identical.
• Target Sum - Another problem that combines branching recursion with memoization on a composite state, bridging backtracking and dynamic programming.