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.length1 <= n <= 60 <= price[i], needs[i] <= 101 <= special.length <= 100special[i].length == n + 10 <= special[i][j] <= 50special[i][j] is non-zero for 0 <= j <= n - 1.Problem Overview: You are given individual item prices, special bundle offers, and the number of items you need to buy. Each special offer contains quantities of items plus a discounted bundle price. The goal is to compute the minimum cost to satisfy the exact shopping needs without buying extra items.
The tricky part is that applying offers creates many combinations of states. Each state represents the remaining items you still need to buy. Efficient solutions treat this as a search problem with overlapping subproblems.
Approach 1: DFS with Memoization (Backtracking + State Caching) — Time: O(k * states), Space: O(states)
This approach models the problem as a recursive search over all valid ways to apply special offers. At any step, you either buy remaining items individually or apply one of the special offers if it does not exceed the current needs. The key observation: many different sequences of offers lead to the same remaining needs state.
Use depth‑first search to explore offers and represent the state as the remaining items vector. Store results in a memoization map where the key is the current needs tuple. If the state appears again, return the cached minimum cost instead of recomputing. Each recursive step iterates through offers, subtracts quantities if valid, and recursively solves the reduced state. This significantly prunes the exponential search space.
This technique combines backtracking with memoization. The baseline cost for each state is buying remaining items individually using the price array. Then try applying each offer to see if it lowers the cost.
Approach 2: Dynamic Programming (State Compression / Bottom-Up) — Time: O(states * offers), Space: O(states)
The problem can also be framed as a multidimensional dynamic programming problem. Each state represents a specific combination of purchased quantities for all items. The DP value stores the minimum cost required to reach that state.
Instead of recursion, iterate through possible states and update costs by applying offers. If there are at most 6 item types (as in the problem constraints), you can encode the quantities using a compressed state representation such as a tuple or a mixed-base integer mask. Each transition corresponds to applying an offer and updating the DP table if the resulting quantities stay within the required needs.
This method relies heavily on representing item counts efficiently using arrays or compressed integers, making it closely related to dynamic programming with state compression. Compared to DFS, the bottom-up approach is more explicit but can require iterating through many states even if they are not reachable.
Recommended for interviews: DFS with memoization is the expected solution. It demonstrates the ability to recognize overlapping subproblems and reduce exponential backtracking using caching. Starting with a naive recursive exploration shows understanding of the search space, while adding memoization converts it into an efficient dynamic programming solution.
This approach uses a combination of Depth First Search (DFS) and memoization to explore all possible ways to purchase the desired items. Memoization is used to store the states that we have already computed, which helps to avoid redundant calculations and speeds up the process.
The idea is to recursively try every combination of buying items using individual purchases and available special offers. For each combination, calculate the remaining needs and the cost so far. If a certain state (combination of needs) has already been computed, retrieve the result from memo to save computation.
The solution defines a recursive function dfs that represents the cost of satisfying the current 'needs'. It uses memoization to save and reuse the results of subproblems, identified by current 'needs' state represented as a tuple.
We calculate the cost of fulfilling the current needs without any special offer. Then, for each offer, we check if that offer is valid by ensuring we don't exceed the current needs. If valid, we recursively calculate the cost using this offer and update the minimum.
Python
JavaScript
Time Complexity: O(2^n * m) where n is the number of items and m is the number of special offers. In the worst case, each combination could take O(m).
Space Complexity: O(n + m), due to memoization storage of states and recursive stack space.
This approach employs Dynamic Programming (DP) to solve the problem, considering each combination of remaining needs as a separate subproblem. The DP table (or dictionary/map) stores minimal costs for fulfilling certain needs, calculated iteratively in a bottom-up manner.
Instead of using recursion, this method explicitly builds up solutions for increasingly larger and more complex needs, leveraging already computed simpler results, thereby improving efficiency.
This Java solution utilizes a depth-first approach with dynamic programming to avoid recursively recalculating costs for the same 'needs'. It stores previously calculated results in a hash map that dynamically maintains the cost for a given state of needs.
The cost is initialized with the direct purchase amount of the remaining needs, and iteratively recalculated when checking valid special offers.
Time Complexity: O(2^n * m), with each unique state of needs potentially considering all m special offers.
Space Complexity: O(k) where k is the number of unique states of needs stored in DP map.
We notice that the number of types of items n leq 6 in the problem, and the quantity of each item needed does not exceed 10. We can use 4 binary bits to represent the quantity of each item needed. Thus, we only need at most 6 times 4 = 24 binary bits to represent the entire shopping list.
First, we convert the shopping list needs into an integer mask, where the quantity of the i-th item needed is stored in the i times 4 to (i + 1) times 4 - 1 bits of mask. For example, when needs = [1, 2, 1], we have mask = 0b0001 0010 0001.
Then, we design a function dfs(cur), representing the minimum amount of money we need to spend when the current state of the shopping list is cur. Therefore, the answer is dfs(mask).
The calculation method of the function dfs(cur) is as follows:
cur without using any bundles, denoted as ans.offer. If the current shopping list cur can use the bundle offer, i.e., the quantity of each item in cur is not less than that in the bundle offer, then we can try to use this bundle. We subtract the quantity of each item in the bundle offer from cur, obtaining a new shopping list nxt, then recursively calculate the minimum cost of nxt and add the price of the bundle offer[n], updating ans, i.e., ans = min(ans, offer[n] + dfs(nxt)).ans.To avoid repeated calculations, we use a hash table f to record the minimum cost corresponding to each state cur.
The time complexity is O(n times k times m^n), where n represents the types of items, and k and m respectively represent the number of bundles and the maximum demand for each type of item. The space complexity is O(n times m^n).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| DFS with Memoization | Time Complexity: O(2^n * m) where n is the number of items and m is the number of special offers. In the worst case, each combination could take O(m). |
| Dynamic Programming | Time Complexity: O(2^n * m), with each unique state of needs potentially considering all m special offers. |
| State Compression + Memoization Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Memoization | O(k * states) | O(states) | Best general solution when exploring offer combinations with overlapping states |
| Dynamic Programming (State Compression) | O(states * offers) | O(states) | Useful when enumerating all purchase states or implementing bottom-up DP |
LeetCode 638. Shopping Offers Explanation and Solution • happygirlzt • 5,680 views views
Watch 9 more video solutions →Practice Shopping Offers with our built-in code editor and test cases.
Practice on FleetCode