Javascript: dfs with & without memo
\nvar closestCost = function(baseCosts, toppingCosts, target) {\n    let res = Infinity;\n    \n    function dfs(tIdx, cur) {\n        if(Math.abs(target-cur) <
```\nvar closestCost = function(baseCosts, toppingCosts, target) {\n    let res = Infinity;\n    \n    function dfs(tIdx, cur) {\n        if(Math.abs(target-cur) < Math.abs(target-res) ||(Math.abs(target-cur) === Math.abs(target-res) && cur < target)) {\n            res = cur;\n        }\n        \n        if(cur > target || tIdx >= toppingCosts.length) {\n            return;\n        }\n        \n        dfs(tIdx + 1, cur);\n        dfs(tIdx + 1, cur + toppingCosts[tIdx]);\n        dfs(tIdx + 1, cur + toppingCosts[tIdx] * 2); \n    }\n    \n    for(const base of baseCosts) {\n        dfs(0, base);\n    }\n   return res;  \n};\n```\n\nSimilar idea to use **memo**, memo the best cost at current `index with current cost`:\n```\nvar closestCost = function(baseCosts, toppingCosts, target) {\n    let res = Infinity;\n    let memo;\n    function dfs(tIdx, cur) {\n        const key = tIdx+\':\'+ cur;\n        if(memo.has(key)) {\n            return memo.get(key);\n        }\n        \n        if(cur > target || tIdx >= toppingCosts.length) {\n            return cur;\n        }\n        \n        // find the closest cost at current position\n        let cost1 = dfs(tIdx + 1, cur);\n        let cost2 = dfs(tIdx + 1, cur + toppingCosts[tIdx]);\n        let cost3 = dfs(tIdx + 1, cur + toppingCosts[tIdx] * 2); \n        const arr = [cost1, cost2, cost3].sort((a,b)=>{\n            if( Math.abs(target-a) === Math.abs(target-b)) {\n                if(a<target) {\n                    return -1;\n                }\n                return 1;\n            }\n            return Math.abs(target-a) - Math.abs(target-b);\n        });\n        \n        memo.set(key, arr[0]);\n        return arr[0];\n    }\n    \n    for(const base of baseCosts) {\n        memo = new Map(); // key = index & cost\n        const cur = dfs(0, base);\n        if(Math.abs(target-cur) < Math.abs(target-res) ||(Math.abs(target-cur) === Math.abs(target-res) && cur < target)) {\n            res = cur;\n        }\n    }\n   return res;  \n};\n```
['JavaScript']