Java Recursion With Actual Backtracking 0ms
Java recursion with actual backtracking.\nSince we need exactly one base, iterate through the bases.\nWith each base ice cream cost, try out all the toppings. F
Java recursion with actual backtracking.\nSince we need exactly one base, iterate through the bases.\nWith each base ice cream cost, try out all the toppings. For each topping, there are three options: 0/1/2 of each topping. Recurse into each of these options for the next topping. \n\nBacktracking: stop recursion if cost already exceeds target since each topping has positive costs, we cannot get closer after exceeding.\n\n\n```java\nclass Solution {\n    /** Closest cost result */\n    int closestCost = Integer.MAX_VALUE;\n    /** Difference between closest cost result and target so far */\n    int closestCostDiff = Integer.MAX_VALUE;\n\n    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {\n        for (int base : baseCosts) {\n            dfs(toppingCosts, 0, base, target);\n        }\n        return closestCost;\n    }\n\n    public void dfs(int[] toppingCosts, int toppingIndex, int cost, int target) {\n        int costDiff = Math.abs(target - cost);\n        if (costDiff < closestCostDiff || (costDiff == closestCostDiff && cost < closestCost)) {\n            closestCostDiff = costDiff;\n            closestCost = cost;\n        }\n        \n        // Since toppings are all positive cost, stop dfs early if cost exceeds target\n        if (toppingIndex >= toppingCosts.length || cost > target)\n            return;\n\n        dfs(toppingCosts, toppingIndex + 1, cost, target);\n        dfs(toppingCosts, toppingIndex + 1, cost + toppingCosts[toppingIndex], target);\n        dfs(toppingCosts, toppingIndex + 1, cost + 2 * toppingCosts[toppingIndex], target);\n    }\n}\n```
['Backtracking', 'Depth-First Search', 'Recursion', 'Java']