General approach to dealing with combinations

This problem is yet another "combinations" problem, a common LC and interview question, here it is: Closest Dessert Cost - LeetCode

1774. Closest Dessert Cost

Medium

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:

• There must be exactly one ice cream base.
• You can add one or more types of topping or have no toppings at all.
• There are at most two of each type of topping.

You are given three inputs:

• baseCosts, an integer array of length n, where each baseCosts[i] represents the price of the ith ice cream base flavor.
• toppingCosts, an integer array of length m, where each toppingCosts[i] is the price of one of the ith topping.
• target, an integer representing your target price for dessert.

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:

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

Accepted

4,882

Submissions

9,974

As the hint says (and yes, I look at hints too from time to time), no need for DP since the limits are small enough. This is a combination algorithm, basically you want to iterate thru all the possibilities. The base cost will always be one of them, so we can discard it from the general idea.

The general idea here is that you want to try 0, 1, 2, 3, ..., N of the "topping costs". In the case here N = 2. The general idea is expressed in the picture below, but goes as follows:

1/ Create a base case checking whether the current value that you're carrying on is the best.
2/ Keep track of how many "toppings" have been used. You can only backtrack if you have not exceeded the max allowed (in this case N=2).
3/ One of the key points in order to improve the performance is to carry along the index of the current topping used. You don't want to start the loop always from index = 0. This will lead to exponential execution time and time-limit-exceeded. You always want to start the loop from index onwards (which makes sense, if you already added all the toppings for index "i", there is no reason to even try that again for indexes less than i, you'll be doing a lot of duplicated calculations which will lead to very slow execution time.

Code is down below, cheers, ACC.

public int ClosestCost(int[] baseCosts, int[] toppingCosts, int target)
{
    int closestCost = Int32.MaxValue;

    foreach (int b in baseCosts)
        ClosestCost(b, target, toppingCosts, new int[toppingCosts.Length], 0, 2, ref closestCost);

    return closestCost;
}

private void ClosestCost(int currentCost,
                            int targetCost,
                            int[] toppingCosts,
                            int[] numberToppingsUsed,
                            int currentToppingsIndex,
                            int maxNumberToppings,
                            ref int closestCost)
{
    if ((Math.Abs(currentCost - targetCost) < Math.Abs(closestCost - targetCost)) ||
            (Math.Abs(currentCost - targetCost) == Math.Abs(closestCost - targetCost) && currentCost < closestCost))
        closestCost = currentCost;

    for (int i = currentToppingsIndex; i < toppingCosts.Length; i++)
    {
        if (numberToppingsUsed[i] < maxNumberToppings)
        {
            numberToppingsUsed[i]++;
            ClosestCost(currentCost + toppingCosts[i], targetCost, toppingCosts, numberToppingsUsed, i, maxNumberToppings, ref closestCost);
            numberToppingsUsed[i]--;
        }
    }
}