# C++ DFS AC solution

• ``````    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
int n = price.size();

int num_offer = special.size();

int ans = 0;
for(int i = 0 ; i < n; i++){
ans += needs[i] * price[i];
}
search(price, special, needs, 0, num_offer, ans, 0);
return ans;
}

void search(vector<int>& price, vector<vector<int>> & special, vector<int>& needs, int idx, int n, int& ans, int pre){
int maxi_num = numeric_limits<int>::max();
if(idx >= special.size()) return;
for(int i = 0; i < needs.size(); i++){ // maxi_num is maximum number of idx_th offer we can use
if(special[idx][i] == 0) continue;
maxi_num = min(maxi_num, needs[i] / special[idx][i]);
}

search(price, special, needs, idx + 1, n, ans, pre); // do not use offer idx;

for(int i = 1; i <= maxi_num; i++){
vector<int> need = needs;
int cur = special[idx].back() * i + pre;
int current = cur;
for(int j = 0; j < need.size(); j++){ // use i offers
need[j] -= special[idx][j] * i;
cur += need[j] * price[j];
}
search(price, special, need, idx + 1, n, ans, current);

ans = min(ans, cur);
}
}``````

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