Leetcode 377. Combination Sum IV Javascript Memoization attempt

Question

Problem Statement

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target. The answer is guaranteed to fit in a 32-bit integer. Input: nums = [1,2,3], target = 4 Output: 7 Explanation: The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) Note that different sequences are counted as different combinations. 

I am new to dynamic programming and am trying to implement a top-down memoization approach instead of using a bottom up tabulation approach as per usual practice. This is my attempt at implementing. Have also left the Map and Javascript object variants in the code in case it is useful for discussion.

var combinationSum4 = function(nums, target) { // const myDict = {}; const myDict = new Map(); const ans = memoCombinationSum4(nums, target, myDict) return ans; } var memoCombinationSum4 = function(nums, target, myDict) { if (target === 0) { myDict[target] = 1; // myDict.set(target, 1); return 1; } else if (target < 0) { return 0; } let total = 0; for (let ele of nums) { if (!myDict[target - ele]) { total+= memoCombinationSum4(nums, target - ele, myDict) } else { total += myDict[target - ele] // total += myDict.get(target - ele); } } // myDict.set(target, total); myDict[target] = total; return total; } 

It passes all basic test cases and got “Time Limit Exceeded” at the following input

var nums = [10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,470,480,490,500,510,520,530,540,550,560,570,580,590,600,610,620,630,640,650,660,670,680,690,700,710,720,730,740,750,760,770,780,790,800,810,820,830,840,850,860,870,880,890,900,910,920,930,940,950,960,970,980,990,111]; var target = 999 

Can anyone tell me what I’m missing out here? Not sure whether I have implemented my modification from the naïve recursive approach correctly or there is something about Javascript I have missed out which is causing the time limit to be exceeded. Let me know if more information is required to solve the problem.

Answer 1

Making memoziation super-easy to read

The common pattern of memoization looks something like this:

const fun = function(param) { if (memo[param] !== undefined) return memo[param]; // compute the actual answer, for "param" let answer = ... memo[param] = answer; return answer; }; 

That is, the first thing that happens in the function is checking if the answer is already in the memoization cache. If yes, return it, otherwise carry on with the regular computation. At the end of the function, put the answer into the cache, and then return it. The memoization cache is not referenced anywhere else in the function, only at the very beginning and at the very end. This is very easy to understand.

The posted code can be refactored to fit this pattern, and it will be easier to focus on the main logic of the computation.

And I recommend renaming myDict to memo or cache.

Using a local function

Instead of passing around nums and myDict as function parameters, you could make memoCombinationSum4 a local function, and let it use those variables in its context:

const memo = new Map(); memo[0] = 1; const memoCombinationSum4 = function(target) { // use memo as in the earlier example // ... // nums is available from the enclosing context // ... }; return memoCombinationSum4(target); 

Stop trying targets that are too high

Notice that if nums is sorted, then when an element is higher than the target, you don't need to check the renaming values:

var combinationSum4 = function(nums, target) { const sorted = [...nums].sort((a, b) => a - b); const memo = new Map(); memo[0] = 1; const memoCombinationSum4 = function(target) { if (memo[target] !== undefined) { return memo[target]; } let total = 0; for (const num of sorted) { if (target < num) break; total += memoCombinationSum4(target - num); } memo[target] = total; return total; }; return memoCombinationSum4(target); } 

Answer 2

If you tried logging what happens you would probably be able to figure it out :D

The good part is that it has nothing to do with your program, but it has to do with JS.

 if (!myDict[target - ele]) { total+= memoCombinationSum4(nums, target - ele, myDict) } 

If myDict = { 1: 0 }, then !myDict[1] is true. Welcome to the world of pain that is JS.

The solution is:

 if (myDict[target - ele] === undefined) { total += memoCombinationSum4(nums, target - ele, myDict) } 

It still takes some seconds (I have no idea what is the time constraint), but at least it completes :D