[ Java 1ms ] Beats runtime of 100% java solutions
\nclass Solution {\n    \n    int l, h;\n    public void applyToppings(int[] a, int[] toppingCosts, int target, int sum) {\n        if (sum >= target) {\n      
```\nclass Solution {\n    \n    int l, h;\n    public void applyToppings(int[] a, int[] toppingCosts, int target, int sum) {\n        if (sum >= target) {\n            \n            if(sum < h || h == -1 || sum == target) {\n                h = sum;\n            }\n\t\t\t// Do not apply anymore toppings, since sum is already greater than target, \n\t\t\t// If we apply more toppings, we\'ll be moving away from target\n            return;\n        }\n        if (sum <= target && (sum > l || l == -1)) {\n            l = sum;\n        }\n        for(int i = toppingCosts.length - 1; i >= 0; i--) {\n            if(a[i] > 0) {\n\t\t\t    // Add ith topping\n                sum += toppingCosts[i];\n                a[i]--;\n                applyToppings(a, toppingCosts, target, sum);\n\t\t\t\t\n\t\t\t\t// Backtrack\n                sum -= toppingCosts[i];\n                a[i]++;\n            }\n        }\n        \n    }\n    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {\n        int[] a = new int[toppingCosts.length]; // available amount of each topping\n        Arrays.fill(a, 2);\n        l = -1; // Closest value lower than target\n        h = -1; // Closest value larger than target\n        Arrays.sort(toppingCosts);\n        for(int i = 0; i < baseCosts.length; i++) {\n            applyToppings(a, toppingCosts, target, baseCosts[i]);\n        }\n        \n\t\t// Check which value is closer to target\n        int diffl = target - l;\n        int diffh = h - target;\n        if(l != -1 && h != -1) {\n            if(diffl < diffh) {\n                return l;\n            } else if (diffl > diffh) {\n                return h;\n            } else {\n                return l;\n            }\n        } \n        if (l != -1) {\n            return l;\n        }\n        return h;\n    }\n}\n```\n\n
['Backtracking', 'Recursion', 'Java']