Let's take a look at the structure of the data:

*There are at most 6 kinds of items, 100 special offers.
For each item, you need to buy at most 6 of them.*

We can see that:

- applying offers decrease amount at least by one
- max usage number of the same offer is 6

It would be easier to think about this problem as of a tree.

Every offer is a node, and it can have at most 6 edges (numbers of times an offer was used). The tree depth is 100.

The running time is ~6^100 and space complexity is ~100 (depth of recursion/tree)

The memorization is not needed because all combinations (paths) with promotions are unique.

```
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
int[] needsArray = new int[needs.size()];
for(int i = 0; i < needsArray.length;i++) {
needsArray[i] = needs.get(i);
}
return minAmount(price, special, needsArray) ;
}
int minAmount(List<Integer> price, List<List<Integer>> specials, int[] needs) {
int amountToPay = 0;
if (specials.isEmpty()) {
// There are no special offers, so just buying the needed amount
for (int i = 0; i < needs.length; i++) {
amountToPay += needs[i] * price.get(i);
}
return amountToPay;
}
List<Integer> special = specials.remove(specials.size() - 1);
int minAmount = Integer.MAX_VALUE;
boolean canApplyOffer = true;
int count = 0;
final int offerPriceIndex = needs.length;
while (canApplyOffer) {
amountToPay = minAmount(price, specials, needs);
minAmount = Math.min(minAmount, special.get(offerPriceIndex) * count + amountToPay);
for (int j = 0; j < needs.length; j++) {
needs[j] -= special.get(j);
if (needs[j] < 0) {
canApplyOffer = false;
}
}
count++;
}
// Restore "needs" array
for (int i = 0; i < needs.length; i++) {
needs[i] += special.get(i) * count;
}
// Restore offers list
specials.add(special);
return minAmount;
}
```