# Simple recursive solution

• Either take the ith offer multiple times, or do not take it at all. If I take the offer, I use the function recursively by updating the needs called "new needs". Quite simple, right ?. Exponential time complexity and linear space complexity because of recursive stack.

``````class Solution {
public:
int recurse(int i,vector<int>& price, vector<vector<int>>& special, vector<int> needs) {
if(i==special.size()){
int base=0;
for(int k=0;k<needs.size();k++){
base += (price[k]*needs[k]);
}
return base;
}
int a = recurse(i+1,price,special,needs);
int flag=1;
int cost=0;
vector<int> new_needs;
int min = INT_MAX;
for(int k=0;k<needs.size();k++){
if(special[i][k]!=0 && needs[k]/special[i][k]<min)
min=needs[k]/special[i][k];
if(special[i][k]<=needs[k]){
//cost += (needs[k]-special[i][k])*price[k];
new_needs.push_back(needs[k]-special[i][k]);
}
else
flag=0;
}
if(flag==1){
if(min==1)
cost += special[i][special[i].size()-1]+recurse(i+1,price,special,new_needs);
else{
new_needs.clear();
for(int k=0;k<needs.size();k++){
new_needs.push_back(needs[k]-(min*special[i][k]));
}
cost += (min*special[i][special[i].size()-1])+recurse(i+1,price,special,new_needs);
}
return a>cost?cost:a;
}
else
return a;
}
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
return recurse(0,price,special,needs);
}
};
``````

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