My Backtracking TLE solution and my explanation for its failure
So my solution hits Time Limit Exceeded. My solution basically tries to add 1 topping at a time and maintains counts for each topping, int[] toppingCounts that 
So my solution hits Time Limit Exceeded. My solution basically tries to add 1 topping at a time and maintains counts for each topping, ```int[] toppingCounts``` that we use backtracking to restore.\n\nMy TLE Backtracking code:\n```\nclass Solution {\n    int smallestDistance = Integer.MAX_VALUE;\n    int bestCost = 0;\n    \n    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {\n        Arrays.sort(toppingCosts);\n        int[] toppingCounts = new int[toppingCosts.length];\n        for(int baseCost : baseCosts) {\n            dfs(baseCost, target, toppingCosts, toppingCounts);\n        }\n        return bestCost;\n    }\n    \n    private void dfs(int soFar, int target, int[] toppingCosts, int[] toppingCounts) {\n        int testDist = Math.abs(target - soFar);\n        if (testDist <= smallestDistance) {\n            if (testDist < smallestDistance) {\n                // found better one\n                smallestDistance = testDist;\n                bestCost = soFar;\n            } else {\n                // tiebreak with min cost\n                bestCost = Math.min(bestCost, soFar);\n            }\n        }\n        \n        if (soFar >= target) {\n            // as all prices positive, done adding toppings...\n            // ...More toppings would only take us further higher from target\n            return;\n        }\n        for(int i=0; i<toppingCosts.length; i++) {\n            if (toppingCounts[i] == 2) {\n                // already have 2 of this topping, can\'t add any more\n                continue;\n            }\n            int toppingCost = toppingCosts[i];\n            toppingCounts[i]++;\n            int costWithTopping = soFar + toppingCost;\n            dfs(costWithTopping, target, toppingCosts, toppingCounts);\n            // backtrack\n            toppingCounts[i]--;\n            if (costWithTopping >= target) {\n                break;\n            }\n        }\n    }\n}\n```\nI was annoyed that my (imo extremely straight-forward )solution failed, so I went to Discuss and looked at the solution basically everyone put where you consider for each topping, include it 0, 1, or 2 times and recurse on the remaining toppings to the right.\n\nExample most-upvoted solution from vikrant_pc I copied below for reference:\n```\nclass Solution {\n    int result;\n    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {\n        result = baseCosts[0];\n        for(int base: baseCosts)\n            helper(base, toppingCosts, 0, target);\n        return result;\n    }\n    private void helper(int current, int[] toppingCosts, int index, int target) {\n        if( Math.abs(target - current) < Math.abs(target - result) || Math.abs(target - current) == Math.abs(target - result) && current < result)\n            result = current;\n        if(index==toppingCosts.length || current >= target) return;\n        helper(current, toppingCosts, index + 1, target);\n        helper(current + toppingCosts[index], toppingCosts, index + 1, target);\n        helper(current + toppingCosts[index]*2, toppingCosts, index + 1, target);\n    }\n}\n```\n\nMy immediate question was, what\'s the difference with this solution and mine? Aren\'t both of them just exhaustively traversing all possibilities so isn\'t this just a stylistic difference?\n\nBut upon closer examination, I noticed that the recommended solution kind of sweeps left to right (```helper(index)``` recurses on ```helper(index + 1)```) along the ```toppingCosts``` so in the recursion tree if you\'re dealing with topping ```J``` and then all contributions of topping ```I``` where ```index of I < index of J in toppingCosts``` have already been taken into account in ancestors of this node. Ex. say we want 2 of topping ```I``` and 1 of topping ```J``` in our solution. Then the correct recommended solution\'s recursion tree would have a branch where we choose 2 of topping ```I``` then recurse and choose 1 of topping ```J```.  Let\'s write this branch as ```() -> choose 2 I -> choose 1 J```\n\nBut in my solution, we can arrive at 2I, 1J **in multiple ways** as we don\'t respect the predecessor toppings being ancestors property mentioned in last paragraph:\n```() -> choose I -> choose I -> choose J``` or ```() -> choose I -> choose J -> choose I``` or ```() -> choose J -> choose I -> choose I``` so we end up doing tons of excess duplicate work as we have extra copies of subtrees of exponential size which is very bad.\n\nEdit:\nI very slightly modified my code to fix the TLE by using this left->right increasing index concept:\nNew Passing Code: \n```\nclass Solution {\n    int smallestDistance = Integer.MAX_VALUE;\n    int bestCost = 0;\n    \n    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {\n        Arrays.sort(toppingCosts);\n        int[] toppingCounts = new int[toppingCosts.length];\n        for(int baseCost : baseCosts) {\n            dfs(0, baseCost, target, toppingCosts, toppingCounts);\n        }\n        return bestCost;\n    }\n    \n    private void dfs(int pos, int soFar, int target, int[] toppingCosts, int[] toppingCounts) {\n        int testDist = Math.abs(target - soFar);\n        if (testDist <= smallestDistance) {\n            if (testDist < smallestDistance) {\n                // found better one\n                smallestDistance = testDist;\n                bestCost = soFar;\n            } else {\n                // tiebreak with min cost\n                bestCost = Math.min(bestCost, soFar);\n            }\n        }\n        \n        if (soFar >= target) {\n            // as all prices positive, done adding toppings...\n            // ...More toppings would only take us further higher from target\n            return;\n        }\n        for(int i=pos; i<toppingCosts.length; i++) {\n            if (toppingCounts[i] == 2) {\n                // already have 2 of this topping, can\'t add any more\n                continue;\n            }\n            int toppingCost = toppingCosts[i];\n            toppingCounts[i]++;\n            int costWithTopping = soFar + toppingCost;\n            dfs(i, costWithTopping, target, toppingCosts, toppingCounts);\n            // backtrack\n            toppingCounts[i]--;\n            if (costWithTopping >= target) {\n                break;\n            }\n        }\n    }\n}\n```\nNote that ```dfs``` takes now takes a ```pos``` argument that is the left most topping index and in our ```for``` loop we recursively call ```dfs(i,...)```. This ensures that for all ```I``` where when we call ```dfs(I,...)``` all nested descendant recursive calls will take the form ```dfs(J,...)``` for all ```J```  where ```J >=I```. And this ```J>=I``` constraint is key.
['Java']