Shopping Offers - Video Solutions

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.