Shopping offers

Array Dynamic Programming Backtracking Bit Manipulation Memoization Bitmask

52.3% acceptance

Feb 20, 2026

1626

790

Given price, special offers, and needs arrays, return the lowest price you have to pay for exactly the items specified in needs.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;
impl Solution {
  pub fn shopping_offers(price: Vec<i32>, special: Vec<Vec<i32>>, needs: Vec<i32>) -> i32 {
    fn dfs(
      needs: &[i32],
      special: &[Vec<i32>],
      price: &[i32],
      memo: &mut HashMap<Vec<i32>, i32>,
    ) -> i32 {
      if let Some(&v) = memo.get(needs) {
        return v;
      }
      // Cost without any special offers
      let mut min_cost: i32 = needs.iter().zip(price.iter()).map(|(&n, &p)| n * p).sum();
      // Try each offer
      'outer: for offer in special {
        let mut new_needs = needs.to_vec();
        for i in 0..needs.len() {
          if offer[i] > new_needs[i] {
            continue 'outer;
          }
          new_needs[i] -= offer[i];
        }
        let cost = offer[needs.len()] + dfs(&new_needs, special, price, memo);
        min_cost = min_cost.min(cost);
      }
      memo.insert(needs.to_vec(), min_cost);
      min_cost
    }
    let mut memo = HashMap::new();
    dfs(&needs, &special, &price, &mut memo)
  }
}