Skip to content

638. Shopping Offers

  • Time: $O(|\texttt{special}||\texttt{needs}|k)$, where $k = \text{max of needs} = 6$
  • Space: $O(6)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
 public:
  int shoppingOffers(vector<int>& price, vector<vector<int>>& special,
                     vector<int>& needs) {
    return dfs(price, special, needs, 0);
  }

 private:
  int dfs(const vector<int>& price, const vector<vector<int>>& special,
          vector<int>& needs, int s) {
    int ans = 0;
    for (int i = 0; i < price.size(); ++i)
      ans += price[i] * needs[i];

    for (int i = s; i < special.size(); ++i)
      if (isValid(special[i], needs)) {
        // Use the special[i].
        for (int j = 0; j < needs.size(); ++j)
          needs[j] -= special[i][j];
        ans = min(ans, special[i].back() + dfs(price, special, needs, i));
        // Unuse the special[i] (backtracking).
        for (int j = 0; j < needs.size(); ++j)
          needs[j] += special[i][j];
      }

    return ans;
  }

  // Returns true if this special offer is a valid one.
  bool isValid(const vector<int>& offer, const vector<int>& needs) {
    for (int i = 0; i < needs.size(); ++i)
      if (needs[i] < offer[i])
        return false;
    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
  public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
    return dfs(price, special, needs, 0);
  }

  private int dfs(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int s) {
    int ans = 0;
    for (int i = 0; i < needs.size(); ++i)
      ans += needs.get(i) * price.get(i);

    for (int i = s; i < special.size(); ++i) {
      List<Integer> offer = special.get(i);
      if (isValid(offer, needs)) {
        // Use the special[i].
        for (int j = 0; j < needs.size(); ++j)
          needs.set(j, needs.get(j) - offer.get(j));
        ans = Math.min(ans, offer.get(offer.size() - 1) + dfs(price, special, needs, i));
        // Unuse the special[i] (backtracking).
        for (int j = 0; j < needs.size(); ++j)
          needs.set(j, needs.get(j) + offer.get(j));
      }
    }

    return ans;
  }

  // Returns true if this special offer is a valid one.
  private boolean isValid(List<Integer> offer, List<Integer> needs) {
    for (int i = 0; i < needs.size(); ++i)
      if (offer.get(i) > needs.get(i))
        return false;
    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def shoppingOffers(
      self,
      price: list[int],
      special: list[list[int]],
      needs: list[int]
  ) -> int:
    def dfs(s: int) -> int:
      ans = 0
      for i, need in enumerate(needs):
        ans += need * price[i]

      for i in range(s, len(special)):
        offer = special[i]
        if all(offer[j] <= need for j, need in enumerate(needs)):
          # Use the special[i].
          for j in range(len(needs)):
            needs[j] -= offer[j]
          ans = min(ans, offer[-1] + dfs(i))
          # Unuse the special[i] (backtracking).
          for j in range(len(needs)):
            needs[j] += offer[j]

      return ans

    return dfs(0)