Memoized solution to Combination IV on Leetcode gives TLE when an array is used for caching

While trying to solve Combination IV on Leetcode, I came up with this memoized solution:

def recurse(nums, target, dp):
        
    if dp[target]!=0:
        return dp[target]
    
    if target==0:
        return dp[0]

    for n in nums:
        if n<=target:
            dp[target] += recurse(nums, target-n, dp)
            
    return dp[target]

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        
        dp = [0]*(target+1)
        dp[0] = 1

        return recurse(nums, target, dp)

But this gives me a Time Limit Exceeded error.

Another memoized solution, that uses a dictionary to cache values instead of a dp array, runs fine and does not exceed time limit. The solution is as follows:

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        memo = {}
        def dfs(nums, t, memo):
            if t in memo:
                return memo[t]
            if t == 0:
                return 1
            if t < 0:
                return 0
            res = 0
            for i in nums:
                res += dfs(nums, t-i, memo)
            memo[t] = res
            return res
        return (dfs(nums, target, memo)) 

Why does using a dict instead of an array improve runtime? It is not like we are iterating through the array or dict, we are only using them to store and access values.

EDIT: The test case on which my code crashed is as follows:

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]

target = 999

Answer

The two versions of the code are not the same. In the list version, you keep recursing if your “cached” value is 0. In the dict version, you keep recursing if the current key is not in the cache. This makes a difference when the result is 0. For example, if you try an example with nums=[2, 4, 6, 8, 10] and total=1001, there is no useful caching done in the list version (because every result is 0).

You can improve your list version by initializing every entry to None rather than 0, and using None as a sentinel value to determine if the result isn’t cached.

It’s also easier to drop the idea of a cache, and use a dynamic programming table directly. For example:

def ways(total, nums):
    r = [1] + [0] * total
    for i in range(1, total+1):
        r[i] = sum(r[i-n] for n in nums if i-n>=0)
    return r[total]

This obviously runs in O(total * len(nums)) time.

It’s not necessary here (since total is at most 1000 in the question), but you can in principle keep only the last N rows of the table as you iterate (where N is the max of the nums). That reduces the space used from O(total) to O(max(nums)).