11ms Java Simple Recursive/Backtracking (No Memoization)


  • 0
    S
    public class ShoppingOffers {
        
        public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
    
            Integer[] boughtArr = new Integer[needs.size()];
            Arrays.fill(boughtArr,0);
            List<Integer> bought = Arrays.asList(boughtArr);
            shoppingOffersHelper(price,special,needs,bought,0,0);
            return min;
        }
    
        int min = Integer.MAX_VALUE;
        private void shoppingOffersHelper(List<Integer> price, List<List<Integer>> special, List<Integer> needs, List<Integer> bought,int currentPrice,int currentOfferIndex) {
            for (int i = currentOfferIndex; i < special.size(); i++) {
                List<Integer> currentSpecial = special.get(i);
                if(canAvail(currentSpecial,needs,bought)){
                    currentPrice+=currentSpecial.get(currentSpecial.size()-1);
                    for (int j = 0; j < bought.size(); j++) {
                        bought.set(j,bought.get(j)+currentSpecial.get(j));
                    }
                    shoppingOffersHelper(price,special,needs,bought,currentPrice,i);
    //backtracking
                    for (int j = 0; j < bought.size(); j++) {
                        bought.set(j,bought.get(j)-currentSpecial.get(j));
                    }
                    currentPrice-=currentSpecial.get(currentSpecial.size()-1);
                }
            }
            int priceForRemaining = addRemainingItems(price,bought,needs);
            currentPrice+=priceForRemaining;
            min = Math.min(min,currentPrice);
    
    
        }
    
        private boolean canAvail(List<Integer> currentSpecial,List<Integer> needs,List<Integer> bought) {
            for (int i = 0; i < needs.size(); i++) {
                if(needs.get(i)-bought.get(i)<currentSpecial.get(i)){
                    return false;
                }
            }
            return true;
        }
    
        private int addRemainingItems(List<Integer> price, List<Integer> bought,List<Integer> needs) {
            int priceForRemaining = 0;
            for (int i = 0; i < price.size(); i++) {
                priceForRemaining+=(needs.get(i)-bought.get(i))*price.get(i);
            }
            return priceForRemaining;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.