# Shopping Offers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/shopping-offers)
Canonical: https://scaleengineer.com/dsa/problems/shopping-offers
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Memoization](https://scaleengineer.com/dsa/patterns/memoization), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
**Companies:** [Coupang](https://scaleengineer.com/companies/coupang), [MathWorks](https://scaleengineer.com/companies/mathworks)
---
## Problem
In LeetCode Store, there are `n` items to sell. Each item has a price. However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.

You are given an integer array `price` where `price[i]` is the price of the `ith` item, and an integer array `needs` where `needs[i]` is the number of pieces of the `ith` item you want to buy.

You are also given an array `special` where `special[i]` is of size `n + 1` where `special[i][j]` is the number of pieces of the `jth` item in the `ith` offer and `special[i][n]` (i.e., the last integer in the array) is the price of the `ith` offer.

Return _the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers_. You are not allowed to buy more items than you want, even if that would lower the overall price. You could use any of the special offers as many times as you want.

**Example 1:**

**Input:** price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
**Output:** 14
**Explanation:** There are two kinds of items, A and B. Their prices are $2 and $5 respectively. 
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B. 
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.

**Example 2:**

**Input:** price = [2,3,4], special = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1]
**Output:** 11
**Explanation:** The price of A is $2, and $3 for B, $4 for C. 
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C. 
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C. 
You cannot add more items, though only $9 for 2A ,2B and 1C.

**Constraints:**

* `n == price.length == needs.length`
* `1 <= n <= 6`
* `0 <= price[i], needs[i] <= 10`
* `1 <= special.length <= 100`
* `special[i].length == n + 1`
* `0 <= special[i][j] <= 50`
* The input is generated that at least one of `special[i][j]` is non-zero for `0 <= j <= n - 1`.

# Approaches
## Brute-Force Recursion (Backtracking)
This approach involves exploring all possible combinations of applying special offers through a recursive function. For any given state of `needs`, we have two choices: either buy the remaining items at their individual prices or apply one of the valid special offers. We recursively explore the consequences of applying an offer and take the minimum cost found among all possibilities.
**Time:** Exponential, roughly O(m^D), where `m` is the number of special offers and `D` is related to the total number of items to buy. The function branches for each applicable offer, leading to an exponential number of calls. · **Space:** O(D * n), where D is the maximum depth of the recursion and n is the number of item types. This space is consumed by the recursion call stack.
**Pros:** Simple to understand and implement as it directly models the decision-making process.
**Cons:** Extremely inefficient due to redundant computations for the same subproblems (i.e., the same `needs` vector).; Will likely result in a 'Time Limit Exceeded' (TLE) error on most platforms for non-trivial test cases.
### Explanation
The core idea is a recursive function that calculates the minimum cost for the items listed in the `needs` vector. This function explores every possible path of applying offers. For a given set of needs, it first computes a baseline cost by assuming no special offers are used. Then, it iterates through all special offers. For each offer that can be validly applied (i.e., we need at least as many items as the offer provides), it calculates a new state of needs and recursively calls itself to find the minimum cost for the remaining items. The total cost for this path is the offer's price plus the cost from the recursive call. The function keeps track of the minimum cost found across all these paths. This method is simple to conceive but inefficient because it recalculates the minimum cost for the same `needs` state multiple times if that state can be reached through different sequences of offers.

```java
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
    return backtrack(price, special, needs);
}

private int backtrack(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
    int n = price.size();
    // Cost without any special offers
    int minCost = 0;
    for (int i = 0; i < n; i++) {
        minCost += needs.get(i) * price.get(i);
    }

    // Try to apply each special offer
    for (List<Integer> offer : special) {
        List<Integer> nextNeeds = new ArrayList<>();
        boolean canApply = true;
        for (int i = 0; i < n; i++) {
            if (needs.get(i) < offer.get(i)) {
                canApply = false;
                break;
            }
            nextNeeds.add(needs.get(i) - offer.get(i));
        }

        if (canApply) {
            // If offer is applicable, calculate cost with this offer and recurse
            int costWithOffer = offer.get(n) + backtrack(price, special, nextNeeds);
            minCost = Math.min(minCost, costWithOffer);
        }
    }
    return minCost;
}
```
### Algorithm
1. Define a recursive function `backtrack(price, special, needs)` that returns the minimum cost for the given `needs`.
2. Inside the function, first calculate the cost of buying all items in `needs` individually without any special offers. Let this be `minCost`. This serves as the initial best price for the current state.
3. Iterate through each special offer in the `special` list.
4. For each offer, check if it can be applied. An offer is applicable if the quantity of each item it provides is less than or equal to the corresponding quantity in the current `needs`.
5. If an offer is applicable, create a new `nextNeeds` list by subtracting the items from the offer from the current `needs`.
6. Make a recursive call: `backtrack(price, special, nextNeeds)`. The cost for this path is the offer's price plus the result of the recursive call.
7. Update `minCost` to be the minimum of its current value and the cost calculated in the previous step.
8. After iterating through all offers, return the final `minCost`.

## Recursion with Memoization (Top-Down DP)
This approach optimizes the brute-force recursion by using memoization, a technique central to top-down dynamic programming. It stores the results of subproblems that have already been solved in a cache (like a hash map). By avoiding redundant computations for the same state of `needs`, it significantly improves performance, making it feasible to solve the problem within typical time limits.
**Time:** O(S * m * n), where `S` is the number of states (`Product(needs[i] + 1)`), `m` is the number of special offers, and `n` is the number of item types. While the theoretical worst-case is high, it's effective in practice for the given constraints. · **Space:** O(S * n), where `S` is the number of unique states (which is at most `Product(needs[i] + 1)`) and `n` is the number of item types. This space is primarily for the memoization table.
**Pros:** Much more efficient than brute-force by eliminating redundant calculations.; Guarantees that the minimum cost for each subproblem is computed only once.; This is the standard and accepted solution for this problem given its constraints.
**Cons:** The space complexity can be large if the number of reachable states (distinct `needs` vectors) is high.; The theoretical worst-case time complexity is still high, although it performs well in practice for the given constraints.
### Explanation
We enhance the recursive solution by adding a cache (e.g., a `HashMap`) to store the minimum cost for each unique `needs` vector encountered. The `needs` list serves as the key, and the minimum cost is the value. Before computing the cost for a `needs` state, we first check if the result is already in our cache. If it is, we return the cached value immediately. Otherwise, we compute the result as in the brute-force approach, and before returning, we store the result in the cache for future use. A useful optimization is to filter out 'useless' special offers beforehand. An offer is useless if its price is more expensive than buying the same items individually. This reduces the number of recursive branches to explore at each step, further improving efficiency.

```java
class Solution {
    private Map<List<Integer>, Integer> memo;

    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        memo = new HashMap<>();
        // Filter out useless offers
        List<List<Integer>> filteredSpecial = new ArrayList<>();
        for (List<Integer> offer : special) {
            int individualPrice = 0;
            for (int i = 0; i < price.size(); i++) {
                individualPrice += offer.get(i) * price.get(i);
            }
            if (offer.get(price.size()) < individualPrice) {
                filteredSpecial.add(offer);
            }
        }
        return solve(price, filteredSpecial, needs);
    }

    private int solve(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        if (memo.containsKey(needs)) {
            return memo.get(needs);
        }

        int n = price.size();
        // Cost without any special offers
        int minCost = 0;
        for (int i = 0; i < n; i++) {
            minCost += needs.get(i) * price.get(i);
        }

        // Try to apply each special offer
        for (List<Integer> offer : special) {
            List<Integer> nextNeeds = new ArrayList<>();
            boolean canApply = true;
            for (int i = 0; i < n; i++) {
                if (needs.get(i) < offer.get(i)) {
                    canApply = false;
                    break;
                }
                nextNeeds.add(needs.get(i) - offer.get(i));
            }

            if (canApply) {
                minCost = Math.min(minCost, offer.get(n) + solve(price, special, nextNeeds));
            }
        }

        memo.put(needs, minCost);
        return minCost;
    }
}
```
### Algorithm
1. Initialize a `Map<List<Integer>, Integer> memo` to store results of subproblems.
2. (Optional but recommended) Pre-process the `special` offers list. Remove any offer where the offer price is greater than or equal to the price of buying its items individually. This prunes the search space.
3. Define a recursive helper function `solve(price, special, needs)`.
4. Inside `solve`, first check if the current `needs` state exists as a key in `memo`. If yes, return the stored value.
5. Calculate the cost of fulfilling `needs` by buying all items individually. This is the initial `minCost`.
6. Iterate through each (filtered) special offer.
7. If an offer is applicable, calculate the `nextNeeds` and recursively call `solve(price, special, nextNeeds)`.
8. Update `minCost` with the minimum of its current value and `offer_price + recursive_result`.
9. Before returning, store the computed `minCost` in `memo` with the current `needs` as the key.
10. Return `minCost`.

# Solutions
### Java

```java
class Solution {
public
  int shoppingOffers(List<Integer> price, List<List<Integer>> special,
                     List<Integer> needs) {
    int ans = total(price, needs);
    List<Integer> t = new ArrayList<>();
    for (List<Integer> offer : special) {
      t.clear();
      for (int j = 0; j < needs.size(); ++j) {
        if (offer.get(j) > needs.get(j)) {
          t.clear();
          break;
        }
        t.add(needs.get(j) - offer.get(j));
      }
      if (!t.isEmpty()) {
        ans = Math.min(ans, offer.get(offer.size() - 1) +
                                shoppingOffers(price, special, t));
      }
    }
    return ans;
  }
private
  int total(List<Integer> price, List<Integer> needs) {
    int s = 0;
    for (int i = 0; i < price.size(); ++i) {
      s += price.get(i) * needs.get(i);
    }
    return s;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int shoppingOffers(vector<int> &price, vector<vector<int>> &special,
                     vector<int> &needs) {
    int ans = total(price, needs);
    vector<int> t;
    for (auto &offer : special) {
      t.clear();
      for (int j = 0; j < needs.size(); ++j) {
        if (offer[j] > needs[j]) {
          t.clear();
          break;
        }
        t.push_back(needs[j] - offer[j]);
      }
      if (!t.empty())
        ans = min(ans,
                  offer[offer.size() - 1] + shoppingOffers(price, special, t));
    }
    return ans;
  }
  int total(vector<int> &price, vector<int> &needs) {
    int s = 0;
    for (int i = 0; i < price.size(); ++i)
      s += price[i] * needs[i];
    return s;
  }
};

```

### Python

```python
class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int: def total(price, needs): return sum(price[i] * needs[i] for i in range(len(needs))) ans = total(price, needs) t = [] for offer in special: t . clear() for j in range(len(needs)): if offer[j] > needs[j]: t . clear() break t . append(needs[j] - offer[j]) if t: ans = min(ans, offer[- 1] + self . shoppingOffers(price, special, t)) return ans

```