package leetcode;

import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.com/problems/shopping-offers/
 */
public class Problem638 {
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        return lowestPrice(price, special, needs);
    }

    private static int lowestPrice(List<Integer> prices, List<List<Integer>> specials, List<Integer> needs) {
        int min = Integer.MAX_VALUE;
        for (List<Integer> special : specials) {
            int specialPrice = special.get(special.size() - 1);
            // exclude the last element
            boolean foundSpecial = true;
            for (int i = 0; i < special.size() - 1; i++) {
                if (needs.get(i) - special.get(i) < 0) {
                    foundSpecial = false;
                    break;
                }
            }
            if (foundSpecial) {
                for (int i = 0; i < special.size() - 1; i++) {
                    needs.set(i, needs.get(i) - special.get(i));
                }
                min = Math.min(min, lowestPrice(prices, specials, needs));
                // backtracking
                for (int i = 0; i < special.size() - 1; i++) {
                    needs.set(i, needs.get(i) + special.get(i));
                }
            }
        }
        int total = 0;
        for (int i = 0; i < prices.size(); i++) {
            int price = prices.get(i);
            int num = needs.get(i);
            total += (price * num);
        }
        min = Math.min(min, total);
        return min;
    }

    public static void main(String[] args) {
        Problem638 prob = new Problem638();
        System.out.println(prob.shoppingOffers(
            Arrays.asList(2, 5),
            Arrays.asList(Arrays.asList(3, 0, 5), Arrays.asList(1, 2, 10)),
            Arrays.asList(3, 2))); // 14
//        System.out.println(prob.shoppingOffers(
//            Arrays.asList(2, 3, 4),
//            Arrays.asList(Arrays.asList(1, 1, 0, 4), Arrays.asList(2, 2, 1, 9)),
//            Arrays.asList(1, 2, 1))); // 11
    }
}

@@ -16,33 +16,8 @@
 e;%0A%0A
-import java.util.Arrays;%0A
 impo
@@ -35,16 +35,16 @@
 l.List;%0A
+
 %0A/**%0A * 
@@ -367,16 +367,51 @@
 pecials,
+%0A                                  
  List%3CIn
@@ -1124,16 +1124,31 @@
 , needs)
+ + specialPrice
 );%0A     
@@ -1574,16 +1574,16 @@
 total);%0A
+
         
@@ -1603,518 +1603,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem638 prob = new Problem638();%0A        System.out.println(prob.shoppingOffers(%0A            Arrays.asList(2, 5),%0A            Arrays.asList(Arrays.asList(3, 0, 5), Arrays.asList(1, 2, 10)),%0A            Arrays.asList(3, 2))); // 14%0A//        System.out.println(prob.shoppingOffers(%0A//            Arrays.asList(2, 3, 4),%0A//            Arrays.asList(Arrays.asList(1, 1, 0, 4), Arrays.asList(2, 2, 1, 9)),%0A//            Arrays.asList(1, 2, 1))); // 11%0A    %7D
 %0A%7D%0A

Solve problem 638