Understanding complexity

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 :confused:

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.

//