# DFS + pruning beats 100% python

• regular DFS
picking special offer 2, we don't need to picking special offer 1 again as the combination would be already calculated.
example:
pick sp1,sp1,sp2 is the same as pick sp2, sp1, sp1

``````    def shoppingOffers(self, price, special, needs):
"""
:type price: List[int]
:type special: List[List[int]]
:type needs: List[int]
:rtype: int
"""
self.res = sys.maxint
self.dfs(needs,special,price,0,0)
return self.res

def dfs(self, needs, special, price, currentprice, specialindex):
if needs == [ 0 for x in xrange(len(needs))]:
self.res = min(self.res,currentprice)
return
for x in xrange(specialindex,len(special)):
vaild = True
for y in xrange(len(needs)):
if needs[y] < special[x][y]:
vaild = False
break
if vaild == True:
nextneeds = [needs[a] - special[x][a] for a in xrange(len(needs))]
self.dfs(nextneeds,special,price,currentprice+special[x][-1],x)
for z in xrange(len(needs)):
if needs[z] >= 1:
currentprice += price[z]*needs[z]
self.res = min(self.res,currentprice)
``````

• Best Solution I have ever seen. Fcking awesome!

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