Very Easy to understand JAVA Solution beats 95% with explanation

  • 7

    The idea is very similar to combination sum. In combination sum where each element can be repeated, check each element to see if it can be used (in this case, if the sum doesn't exceed the target). If so, use it. Repeat this until we get the result.

    For this question, we check each promotion offers, if the offer can be used, use it. Repeat the process and find the minimum result. In this question, the condition whether one offer can be used is the number of items in the offer doesn't exceed the needed number. Find the minimum among all combinations.

    The thing to remember, which also happens in real life is that some special offers are actually more expensive than buying each individual item in the offers!!! Thus be smart and compare if buying directly is cheaper.

    here is my code:

    public class Solution {
        public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        	return helper(price, special, needs, 0);
        private int helper(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int pos) {
        	int local_min = directPurchase(price, needs);
        	for (int i = pos; i < special.size(); i++) {
        		List<Integer> offer = special.get(i);
        		List<Integer> temp = new ArrayList<Integer>();
            	for (int j= 0; j < needs.size(); j++) {
            		if (needs.get(j) < offer.get(j)) { // check if the current offer is valid
            			temp =  null;
            		temp.add(needs.get(j) - offer.get(j));
        		if (temp != null) { // use the current offer and try next
        			local_min = Math.min(local_min, offer.get(offer.size() - 1) + helper(price, special, temp, i)); 
        	return  local_min;
        private int directPurchase(List<Integer> price, List<Integer> needs) {
        	int total = 0;
        	for (int i = 0; i < needs.size(); i++) {
        		total += price.get(i) * needs.get(i);
        	return total;

  • 0

    This the most clear method I have seen.

Log in to reply

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