## Shopping Offers

• Time:O(|\texttt{special}||\texttt{needs}|k), where k = \text{max of needs} = 6
• Space:O(6)

## C++

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 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<int>& offer, const vector<int>& needs) {
for (int i = 0; i < needs.size(); ++i)
if (needs[i] < offer[i])
return false;
return true;
}
};


## JAVA

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 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<Integer> offer, List<Integer> needs) {
for (int i = 0; i < needs.size(); ++i)
if (offer.get(i) > needs.get(i))
return false;
return true;
}
}


## Python

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)