[Java] Clean Backtracking with pruning
\n\nclass Solution {\n    int target;\n    int[] toppingCosts;\n\n    int res = Integer.MAX_VALUE;\n    \n    public int closestCost(int[] baseCosts, int[] topp
\n```\nclass Solution {\n    int target;\n    int[] toppingCosts;\n\n    int res = Integer.MAX_VALUE;\n    \n    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {\n        this.target = target;\n        this.toppingCosts = toppingCosts;\n              \n        for (int base : baseCosts) dfs(base, 0);\n  \n        return res;\n    }\n    \n    // idx: current topping index\n    private void dfs(int curr, int idx) {\n        if (idx == toppingCosts.length) return;\n        \n        \n        // try 0, 1, 2 current toppings\n        for (int t = 0; t <= 2; t++) {\n            int next = curr + t * toppingCosts[idx];\n\n            int diff = getDiff(next);\n            \n            // next is already a worse result, no need to add more prices\n            if (diff < 0 && next > res) return;       \n            \n            // next is a better result, update final result\n            if (diff > 0 || (diff == 0 && next < res)) res = next;\n            \n            dfs(next, idx + 1);\n        }\n    }\n    \n    private int getDiff(int curr) {\n        return Math.abs(res - target) - Math.abs(curr - target);\n    }\n}\n```
[]