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& price, vector>& special, vector& needs) { return dfs(price, special, needs, 0); } private: int dfs(const vector& price, const vector>& special, vector& 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 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)); // backtracking - unuse special[i] for (int j = 0; j < needs.size(); ++j) needs[j] += special[i][j]; } return ans; } // check if this special offer is a valid one bool isValid(const vector& offer, const vector& 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 price, List> special, List needs) { return dfs(price, special, needs, 0); } private int dfs(List price, List> special, List 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 offer = special.get(i); if (isValid(offer, needs)) { // use 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)); // backtracking - unuse special[i] for (int j = 0; j < needs.size(); ++j) needs.set(j, needs.get(j) + offer.get(j)); } } return ans; } // check if this special offer is a valid one private boolean isValid(List offer, List 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 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 special[i] for j in range(len(needs)): needs[j] -= offer[j] ans = min(ans, offer[-1] + dfs(i)) # backtracking - unuse special[i] for j in range(len(needs)): needs[j] += offer[j] return ans return dfs(0)