1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Please add a problem statement. \$\endgroup\$
    – vnp
    Aug 28 at 17:38
1
\$\begingroup\$

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);
}
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\begingroup\$ Thank you for your answer, your suggestion works for me. Do you mind adding the reasons why my initial code is causing the slowness? \$\endgroup\$ Oct 7 at 4:48
  • \$\begingroup\$ They were not causing slowness, you literally had infinite recursion, because some elements in myDict had value 0. In other words - if (!myDict[target - ele]) always executed, because if(!0) is true. \$\endgroup\$
    – Blaž Mrak
    Oct 7 at 22:46
  • \$\begingroup\$ Ok I see, so even with cases of target - ele having value 0, which was computed before, the code before change will call the recursion instead of using the cached valued in the object. I guess my next question will be why you said this is a "pain that is JS". Not sure if it's an algorithm flaw now or something unique about JS that I'm not knowing about. \$\endgroup\$ Oct 7 at 23:48
  • \$\begingroup\$ Because js does not have types. What you meant by !map[key] is something like !map.isSet(key) (basically if the key does not yet exist - a null check). You probably went over this multiple times, and didn't notice the bug, because each time you said to your self "if key does not exist, do recursion", came to the end of the program and was like WTF. JS has falsey values - null, undefined, 0, Nan, false AND "", which basically resolve to false in an if statement. With !map[key] this is a null check only if you are sure that the value is an object. \$\endgroup\$
    – Blaž Mrak
    Oct 8 at 10:35
  • \$\begingroup\$ So it is a falsey check and not a null check. And it is easy to forget that because it works most of the time. But JS does not care. As it does not care for something like 5 + '3' and just happily concatenates to '53'. In a typed language you wouldn't have this issue. \$\endgroup\$
    – Blaž Mrak
    Oct 8 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.