# C++ 6ms Straightforward Solution

• Idea: Basically, my method is a brute-force way using DFS. I accelerate it by only diving in next level if the current cost is not greater than some previous total cost. Other explanations are commented in codes.

``````class Solution {
int res = INT_MAX;
void dfs(vector<int>& price, vector<vector<int>>& special, vector<int> needs, int cost){

// Phase 1: if needs are satisified, update result
bool emptyneed = true;
for (int num: needs)
if (num != 0){
emptyneed = false;
break;
}
if (emptyneed) {
res = min(cost, res);
return;
}

// Phase 2: check if there is available special offer
for (int i = 0; i < special.size(); i++){

bool applicable = true;
for (int j = 0 ; j < special[i].size()-1; j++)
if (needs[j] < special[i][j]){
applicable = false;
break;
}

if (applicable) {
int newCost = cost + special[i].back();
if (newCost > res) continue;
// earlier exit, if current cost is already larger than some previous cost

vector<int> newNeeds = needs;
for (int j = 0 ; j < special[i].size()-1; j++)
newNeeds[j] -= special[i][j];
dfs(price, special, newNeeds, newCost);
}
}

// Phase 3: buy products one-by-one
for (int i = 0; i < price.size(); i++){
if (needs[i] == 0) continue;
cost += needs[i]*price[i];
needs[i] = 0;
}
dfs(price, special, needs, cost);
}
public:
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
dfs(price, special, needs, 0);
return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.