The idea is simple. The lowest price shopping should be sum(x[i]*special[i]), where x[i] is the number of times a special offer is taken. The search process is the lowest price among all combinations of specials.
For examples, special =[ [1, 1, 1], ], needs is [2, 2]. Then number of combination is 2(1 or 2 special offers) + 1(no offers) = 3
The search space starts from 0 offers, then incrementally adds one offer based on a previous feasible plan. The new plan and unfilled needs are pushed into the queue. When processing each plan, cost is estimated and min_price is updated accordingly.
To avoid duplicate plans, a plans_created set is maintained.
The time complexity is # of possible offer combinations.
class Solution(object): def shoppingOffers(self, price, special, needs): """ :type price: List[int] :type special: List[List[int]] :type needs: List[int] :rtype: int """ min_cost = sum(x*y for x, y in zip(needs, price)) no_special = tuple(*len(special)) plans_created, q = set([no_special]), collections.deque([(no_special, needs, min_cost)]) while q: (prev_plan, prev_needs, prev_cost) = q.pop() # create new plans for i in xrange(len(special)): needs, plan = prev_needs[:], list(prev_plan) plan[i] += 1 if tuple(plan) in plans_created: continue plans_created.add(tuple(plan)) needs = map(lambda j: needs[j]-special[i][j], xrange(len(price))) if min(needs)<0: continue cost = prev_cost + special[i][-1] - sum([x*y for (x, y) in zip(special[i], price)]) min_cost = min(min_cost, cost) q.appendleft((tuple(plan), needs, cost)) return min_cost