# AC python BFS solution

• 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([0]*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