public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
Map<List<Integer>, Integer> map = new HashMap<>();
return payWithOffers(price, special, needs, map);
public int payWithOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs, Map<List<Integer>, Integer> map) {
if (map.containsKey(needs)) {
int res = payWithoutOffer(price, needs);
for (List<Integer> offer : special) {
List<Integer> needsCopy = new ArrayList<>(needs);
for (int i = 0; i < n; i++) {
if (needsCopy.get(i) < offer.get(i)) {
needsCopy.set(i, needs.get(i) - offer.get(i));
res = Math.min(res, offer.get(n) + payWithOffers(price, special, needsCopy, map));
public int payWithoutOffer(List<Integer> price, List<Integer> needs) {
for (int i = 0; i < price.size(); i++) {
res += price.get(i) * needs.get(i);