title: Target sum (leetcode 494) - Why one code gives TLE but other don't using python dictionary?
body: <p>I recently came across this leetcode question <a href="https://leetcode.com/problems/target-sum/" rel="nofollow noreferrer">Target Sum</a> which i tried to solve using recursion + memoization in Python. But following code gave TLE:</p>
  <pre><code>class Solution:
  def findTargetSumWays(self, nums: List[int], target: int) -&gt; int:
      
      n=len(nums)
      dp={}
      
      def ftsw(i,t):
          if i==len(nums):
              if t==target:
                  return 1
              else:
                  return 0
              
          if dp.get((i,t)):
              return dp.get((i,t))
          
          dp[(i,t)] = ftsw(i+1,t+nums[i])+ ftsw(i+1,t-nums[i])
          return dp[(i,t)]
      
      
      return(ftsw(0,0))
          
  </code></pre>
  <p>But This code didn't:</p>
  <pre><code>class Solution:
  def findTargetSumWays(self, nums: List[int], target: int) -&gt; int:
      
      n=len(nums)
      dp={}
      
      def ftsw(i,t):
          if i==len(nums):
              if t==target:
                  return 1
              else:
                  return 0
              
          if (i,t) in dp:
              return dp[(i,t)] 
          
          dp[(i,t)] =  ftsw(i+1,t+nums[i])+ ftsw(i+1,t-nums[i])
          return dp[(i,t)]
  
          
      
      
      return(ftsw(0,0))
  </code></pre>
  <p>can anyone explain why this happened and how python dictionary take these 2 codes differently?</p>