LeetCode 1774. The dessert cost closest to the target price is one question per day

Problem description

You're going to make dessert , Now you need to buy ingredients . At present, there are n Grow ice cream base and m Kinds of ingredients are available . There are a few rules to follow in making desserts ：

Must choose A kind of Ice cream base .
You can add One or more ingredients , You can also do it without adding any ingredients .
Each type of ingredient Two at most .
Here are three inputs for you ：

baseCosts , A length of n Array of integers for , Each of them baseCosts[i] It means the first one i The price of an ice cream base .
toppingCosts, A length of m Array of integers for , Each of them toppingCosts[i] Express One copy The first i The price of an ice cream ingredient .
target , An integer , Indicates the target price for your dessert .
You want the total cost of your dessert to be as close to the target price as possible target .

Return to the nearest target The cost of desserts . If there are multiple options , return   The cost is relatively low A kind of .

Example 1：

Input ：baseCosts = [1,7], toppingCosts = [3,4], target = 10
Output ：10
explain ： Consider the following combination of options （ All subscripts are from 0 Start ）：
- choice 1 Base material No ： cost 7
- choice 1 Share 0 Ingredient No.1 ： cost 1 x 3 = 3
- choice 0 Share 1 Ingredient No.1 ： cost 0 x 4 = 0
The total cost ：7 + 3 + 0 = 10 .
Example 2：

Input ：baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
Output ：17
explain ： Consider the following combination of options （ All subscripts are from 0 Start ）：
- choice 1 Base material No ： cost 3
- choice 1 Share 0 Ingredient No.1 ： cost 1 x 4 = 4
- choice 2 Share 1 Ingredient No.1 ： cost 2 x 5 = 10
- choice 0 Share 2 Ingredient No.1 ： cost 0 x 100 = 0
The total cost ：3 + 4 + 10 + 0 = 17 . There is no total cost of 18 How to make a dessert .
Example 3：

Input ：baseCosts = [3,10], toppingCosts = [2,5], target = 9
Output ：8
explain ： It can be made at a total cost of 8 and 10 For dessert . return 8 , Because it's a lower cost solution .
Example 4：

Input ：baseCosts = [10], toppingCosts = [1], target = 1
Output ：10
explain ： Be careful , You can choose not to add any ingredients , But you have to choose a base material .
 

Tips ：

n == baseCosts.length
m == toppingCosts.length
1 <= n, m <= 10
1 <= baseCosts[i], toppingCosts[i] <= 104
1 <= target <= 104

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/closest-dessert-cost
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Java

class Solution {
    int ans = Integer.MAX_VALUE;
    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        int n = baseCosts.length;
        for(int i = 0;i < n;i++){
            dfs(toppingCosts,0,baseCosts[i],target);
        }
        return ans;
    }
    public void dfs(int[] toppingCosts,int index,int sum,int target){

        if(Math.abs(sum - target) < Math.abs(ans - target)) ans = sum;
        else if(Math.abs(sum - target) == Math.abs(ans - target)) ans = ans < target ? ans : sum;
        
        // Judge after updating the results 
        if(index == toppingCosts.length || sum >= target) return;

        // Add the ingredients 
        for(int i = 0;i < 3;i++){
            dfs(toppingCosts,index + 1,sum + toppingCosts[index] * i,target);
        }
    }
}