Return to Question

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.

Problem Statement

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

Problem Statement

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.