1
class Solution {
2
  public static int fun(
3
      int index, List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
4
    // Base
5
    if (index < 0) {
6
      int addAmount = 0;
7
      for (int i = 0; i < needs.size(); i++) {
8
        addAmount += (needs.get(i) * price.get(i));
9
      }
10
      return addAmount;
11
    }
12

13
    // Not Take Offer
14
    int notTakeOffer = 0 + fun(index - 1, price, special, new ArrayList<>(needs));
15

16
    // Take Offer
17
    int takeOffer = 1000000000;
18
    if (canTakeOffer(special.get(index), new ArrayList<>(needs))) {
19
      List<Integer> current_special = special.get(index);
20
      for (int i = 0; i < current_special.size() - 1; i++) {
21
        int current_need = needs.get(i);
22
        int update = current_special.get(i);
23
        needs.set(i, current_need - update);
24
      }
25
      takeOffer =
26
          current_special.get(current_special.size() - 1)
27
              + fun(index, price, special, new ArrayList<>(needs));
28
    }
29
    return Math.min(notTakeOffer, takeOffer);
30
  }
31

32
  public static boolean canTakeOffer(List<Integer> current_special, List<Integer> needs) {
33
    boolean canTake = true;
34
    for (int i = 0; i < current_special.size() - 1; i++) {
35
      if (needs.get(i) < current_special.get(i)) {
36
        canTake = false;
37
        break;
38
      }
39
    }
40
    return canTake;
41
  }
42

43
  public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
44
    int items = price.size();
45
    int offers = special.size();
46
    return fun(offers - 1, price, special, needs);
47
  }
48
}