Closest Dessert Cost

You would like to make dessert and are preparing to buy the ingredients. You have n ice cream base flavors and m types of toppings to choose from. You must follow these rules when making your dessert:

You are given three inputs:

You want to make a dessert with a total cost as close to target as possible.

Return the closest possible cost of the dessert to target. If there are multiple, return the lower one.

 

Example 1:

Input: baseCosts = [1,7], toppingCosts = [3,4], target = 10
Output: 10
Explanation: Consider the following combination (all 0-indexed):
- Choose base 1: cost 7
- Take 1 of topping 0: cost 1 x 3 = 3
- Take 0 of topping 1: cost 0 x 4 = 0
Total: 7 + 3 + 0 = 10.

Example 2:

Input: baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
Output: 17
Explanation: Consider the following combination (all 0-indexed):
- Choose base 1: cost 3
- Take 1 of topping 0: cost 1 x 4 = 4
- Take 2 of topping 1: cost 2 x 5 = 10
- Take 0 of topping 2: cost 0 x 100 = 0
Total: 3 + 4 + 10 + 0 = 17. You cannot make a dessert with a total cost of 18.

Example 3:

Input: baseCosts = [3,10], toppingCosts = [2,5], target = 9
Output: 8
Explanation: It is possible to make desserts with cost 8 and 10. Return 8 as it is the lower cost.

Example 4:

Input: baseCosts = [10], toppingCosts = [1], target = 1
Output: 10
Explanation: Notice that you don't have to have any toppings, but you must have exactly one base.
 

Constraints:


Solution:

DFS

class Solution {
    int res = -100000;
    Set<Integer> visited = new HashSet();
    
    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        dfs(baseCosts, toppingCosts, 0, 0, 0, 0, 0, target);
        return res;
    }
    
    private void dfs(int[] base, int[] top, int i, int c, int j, int d, int cost, int target) {
        // if (cost > target) {
        //     return;
        // }
        int hash = Arrays.hashCode(new int[]{i, c, j, d, cost});
        if (!visited.add(hash)) return;
        if (c == 1) {
            if (Math.abs(cost - target) < Math.abs(res - target) || Math.abs(cost - target) == Math.abs(res - target) && cost < res) {
                res = cost;
            }
        }
        if (i < base.length && c == 0) {
            dfs(base, top, i + 1, 1, j, d, cost + base[i], target);
            dfs(base, top, i + 1, 0, j, d, cost, target);
        }
        if (j < top.length) {
            if (d < 2) {
                dfs(base, top, i, c, j, d + 1, cost + top[j], target);
            }
            dfs(base, top, i, c, j + 1, 0, cost, target);
        }
    }
}

class Solution {
    int res = -100000;
    
    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        for (int base : baseCosts) {
            dfs(toppingCosts, 0, base, target);
        }
        return res;
    }
    
    private void dfs(int[] top, int i, int cost, int target) {
        if (Math.abs(cost - target) < Math.abs(res - target) || Math.abs(cost - target) == Math.abs(res - target) && cost < res) {
            res = cost;
        }
        if (i == top.length) return;
        dfs(top, i + 1, cost, target);
        dfs(top, i + 1, cost + top[i], target);
        dfs(top, i + 1, cost + top[i] * 2, target);
    }
}