Just recursively try every possible combination.

Compare how much it costs among retail price (no offer) and using each offer.

Terminate when

(1) The condition met: return accumulated value

(2) The condition violated: not an option, hence infinity

```
def shoppingOffers(self, price, special, needs):
def dfs(remain, acc):
if all(x == 0 for x in remain):
return acc
elif any(x < 0 for x in remain):
return float('inf')
ans = sum(map(lambda x, y: x*y, remain, price))
for spc in special:
ans = min(ans, dfs(map(lambda x, y: x-y, remain, spc[:-1]), spc[-1]))
return ans+acc
return dfs(needs, 0)
```