Problem Description

The Shopping Offers problem asks you to help a shopper buy a list of items at the lowest possible price. You are given three inputs:

• price: An array where each element represents the price of a single unit of an item.
• special: A list of special offers. Each offer is an array where the first N elements indicate how many units of each item are included, and the last element is the total price for the offer.
• needs: An array representing how many units of each item the shopper wants to buy.

Thought Process

At first glance, the problem seems to invite a brute-force approach: try every combination of offers and single purchases, and pick the cheapest. However, this quickly becomes infeasible as the number of items and offers increases, due to the exponential number of combinations.

The key insight is to recognize that the problem can be broken down recursively: for a given set of needs, try every offer that can be applied, recursively solve the subproblem for the remaining needs, and take the minimum. Since many subproblems will repeat (e.g., the same needs state reached via different offer paths), memoization (caching) can help avoid redundant computations.

This approach shifts from brute-force enumeration to a more efficient recursive search with memoization, similar to dynamic programming.

Solution Approach

We use a recursive Depth-First Search (DFS) with memoization to solve the problem efficiently. Here are the steps:

1. Define a recursive function that takes the current needs as its parameter and returns the minimum cost to satisfy those needs.
2. Base case: If all needs are zero, the cost is zero.
3. Try buying items individually: Compute the cost of buying the remaining items at their regular prices.
4. Try each special offer:
   • For each offer, check if it can be applied (i.e., does not exceed any current need).
   • If applicable, subtract the offer's quantities from the current needs and recursively compute the cost for the new needs, adding the offer's price.
5. Memoize the result for the current needs to avoid redundant work.
6. Return the minimum cost found among all possible choices.

We use a hash map (dictionary) for memoization, because lookups and inserts are O(1), which greatly improves performance.

Example Walkthrough

Suppose:

• price = [2, 5] (item 0 costs $2, item 1 costs $5)
• special = [[3,0,5],[1,2,10]] (offer 1: 3 of item 0 for $5; offer 2: 1 of item 0 and 2 of item 1 for $10)
• needs = [3,2] (need 3 of item 0 and 2 of item 1)

1. Base cost: buy everything individually: 3×2 + 2×5 = $6 + $10 = $16
2. Try offer 1: Use it once, now needs = [0,2], cost so far $5
3. For [0,2], only way is to buy 2×item 1 individually: 2×5 = $10, total $15
4. Try offer 2: Use it once, now needs = [2,0], cost so far $10
5. For [2,0], buy 2×item 0 individually: 2×2 = $4, total $14
6. Try both offers: Use offer 1 and offer 2? Not possible since applying both would exceed needs.
7. The minimum is $14.

The recursive function explores all valid combinations, and memoization ensures that repeated states like [2,0] or [0,2] are not recomputed.

Time and Space Complexity

Brute-force: The number of combinations is exponential in the number of items and the maximum need per item. If n is the number of item types and k is the maximum quantity needed for any item, the state space is O(k^n).

Optimized (DFS + Memoization): Each unique needs tuple is computed at most once. Thus, the time and space complexity are both O(k^n), where k is the maximum need and n is the number of items. This is feasible for small n (typically ≤ 6).

Summary

The Shopping Offers problem is a classic example of recursive search with memoization. By breaking the problem into subproblems and caching results, we avoid redundant work and efficiently find the minimum cost. The elegance lies in recognizing the subproblem structure and using a hash map to remember solutions to previously seen states.

Code Implementation

from typing import List
class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        memo = {}
        def dfs(current_needs):
            needs_tuple = tuple(current_needs)
            if needs_tuple in memo:
                return memo[needs_tuple]
            # buy all items at regular price
            min_cost = sum(p * n for p, n in zip(price, current_needs))
            for offer in special:
                new_needs = []
                for i in range(len(price)):
                    if offer[i] > current_needs[i]:
                        break
                    new_needs.append(current_needs[i] - offer[i])
                else:
                    # offer can be used
                    min_cost = min(min_cost, offer[-1] + dfs(new_needs))
            memo[needs_tuple] = min_cost
            return min_cost
        return dfs(needs)
      

class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        unordered_map<string, int> memo;
        return dfs(price, special, needs, memo);
    }
    int dfs(vector<int>& price, vector<vector<int>>& special, vector<int> needs, unordered_map<string, int>& memo) {
        string key = serialize(needs);
        if (memo.count(key)) return memo[key];
        int min_cost = 0;
        for (int i = 0; i < needs.size(); ++i)
            min_cost += needs[i] * price[i];
        for (auto& offer : special) {
            vector<int> new_needs = needs;
            int i = 0;
            for (; i < needs.size(); ++i) {
                if (offer[i] > new_needs[i])
                    break;
                new_needs[i] -= offer[i];
            }
            if (i == needs.size()) {
                min_cost = min(min_cost, offer.back() + dfs(price, special, new_needs, memo));
            }
        }
        memo[key] = min_cost;
        return min_cost;
    }
    string serialize(vector<int>& needs) {
        string res;
        for (int n : needs) res += to_string(n) + ",";
        return res;
    }
};
      

import java.util.*;
class Solution {
    Map<List<Integer>, Integer> memo = new HashMap<>();
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        if (memo.containsKey(needs)) return memo.get(needs);
        int minCost = 0;
        for (int i = 0; i < price.size(); ++i)
            minCost += price.get(i) * needs.get(i);
        for (List<Integer> offer : special) {
            List<Integer> newNeeds = new ArrayList<>();
            int i = 0;
            for (; i < price.size(); ++i) {
                if (offer.get(i) > needs.get(i))
                    break;
                newNeeds.add(needs.get(i) - offer.get(i));
            }
            if (i == price.size()) {
                minCost = Math.min(minCost, offer.get(offer.size() - 1) + shoppingOffers(price, special, newNeeds));
            }
        }
        memo.put(needs, minCost);
        return minCost;
    }
}
      

/**
 * @param {number[]} price
 * @param {number[][]} special
 * @param {number[]} needs
 * @return {number}
 */
var shoppingOffers = function(price, special, needs) {
    const memo = new Map();
    function dfs(currentNeeds) {
        const key = currentNeeds.join(',');
        if (memo.has(key)) return memo.get(key);
        let minCost = 0;
        for (let i = 0; i < price.length; ++i) {
            minCost += price[i] * currentNeeds[i];
        }
        for (const offer of special) {
            let valid = true;
            const newNeeds = [];
            for (let i = 0; i < price.length; ++i) {
                if (offer[i] > currentNeeds[i]) {
                    valid = false;
                    break;
                }
                newNeeds.push(currentNeeds[i] - offer[i]);
            }
            if (valid) {
                minCost = Math.min(minCost, offer[offer.length - 1] + dfs(newNeeds));
            }
        }
        memo.set(key, minCost);
        return minCost;
    }
    return dfs(needs);
};