DP Java backtracking
\nclass Solution {\n  public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {\n    int n = baseCosts.length;\n    int m = toppingCosts.length;
```\nclass Solution {\n  public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {\n    int n = baseCosts.length;\n    int m = toppingCosts.length;\n    \n    int[] toppingCount = new int[m];\n    Map<String, Integer> dp = new HashMap<>();\n    int closest = Integer.MAX_VALUE/2;\n\t\n\t// start the recursion with choosing a base already since a base is mandatory\n    for(int baseCost : baseCosts) {\n      int cost = dfs(baseCost, dp, toppingCosts, target, toppingCount, baseCost, 0);\n      closest = getClosest(cost, closest, target);\n    }\n    \n    return closest;\n  }\n  \n  public int dfs(\n    int base,\n    Map<String, Integer> dp,\n    int[] toppingCosts,\n    int target,\n    int[] toppingCount,\n    int currCost,\n    int currIdx\n  ) {\n    if(currCost >= target) return currCost;\n    if(currIdx >= toppingCount.length) return currCost;\n    String key = String.valueOf(base) + "," + String.valueOf(currCost) + "," + String.valueOf(currIdx);\n    if(dp.containsKey(key)) return dp.get(key);\n    int closest = Integer.MAX_VALUE/2;\n    \n    for(int i = currIdx; i < toppingCosts.length; i++) {\n      if(toppingCount[i] < 2) { // we can only have 2 of the same toppings\n        toppingCount[i]++; // we want to use this topping, so increment\n        int cost1 = dfs(base, dp, toppingCosts, target, toppingCount, currCost+toppingCosts[i], currIdx);   \n        closest = getClosest(cost1, closest, target);\n        toppingCount[i]--; // backtrack\n      }\n\t  // cost2 is the 2nd choice at every recursion. We can choose not to add a topping\n      int cost2 = dfs(base, dp, toppingCosts, target, toppingCount, currCost, currIdx+1);\n      closest = getClosest(cost2, closest, target);\n    }\n    dp.put(key, closest);\n    return closest;\n  }\n  \n  public int getClosest(int cost, int currentClosest, int target) {\n    int closest = currentClosest;\n    if(Math.abs(target-cost) == Math.abs(target-closest)) {\n      closest = Math.min(cost, closest); // choose the smaller one per the question requirements\n    }\n\n    if(Math.abs(target-cost) < Math.abs(target-closest)) {\n      closest = cost;\n    }\n    return closest;\n  }\n}\n```
['Dynamic Programming', 'Backtracking', 'Java']