638. Shopping Offers

Version #1 DFS

69.12 %
class Solution {
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        int curr = 0;
        int N = price.size();
        for (int i = 0; i < N; i++) {
            curr += needs.get(i) * price.get(i);
        }
        // try if we can use any of the special offeres
        for (List<Integer> offer : special) {
            int i = 0;
            List<Integer> next = new ArrayList<>();
            for (i = 0; i < N; i++) {
                if (needs.get(i) < offer.get(i)) { // we can't apply this offer, otherwise exceed #item
                    break;
                }
                next.add(needs.get(i) - offer.get(i));
            }
            if (i == N) { // only try this offer if it is valid for current state
                curr = Math.min(curr, offer.get(i) + shoppingOffers(price, special, next));
            }
        }
        return curr;
    }
}