I was attempting this problem on leetcode where I happened to code this recursive solution with the intent of passing some cases. The complexity of the code I believe is 2^n where n is the number of offers. But the code passed all test cases. Can someone please try explaining how is this possible?
Is it the full code? I think the main function is missing 
On leetcode, we need to just fill in the function shoppingOffers() (given as per the arguments passed). minCost() is created by me.
Oh, i get it then! Thanks.
p = min(p,minCost(price,special,newNeed, index+1, currCost+special[index][special[index].size()-1]));
// using the same offer again
p = min(p,minCost(price,special,newNeed, index, currCost+special[index][special[index].size()-1]));
Wont it simply over-write p’s value with new value? Whats the use of previous computations then, if they will just get over-written in the end?
Yes, it seems to be O(2^n) to me too. I can think that somewhere cause of ‘there can be atmost 6 items and 100 special offers’ the code slipped in. The test cases must be weak, nothing else explains this code passing.