title: Trying to understand the time complexity of this dynamic recursive subset sum
body: <pre><code># Returns true if there exists a subsequence of `A[0…n]` with the given sum
  def subsetSum(A, n, k, lookup):
   
      # return true if the sum becomes 0 (subset found)
      if k == 0:
          return True
   
      # base case: no items left, or sum becomes negative
      if n &lt; 0 or k &lt; 0:
          return False
   
      # construct a unique key from dynamic elements of the input
      key = (n, k)
   
      # if the subproblem is seen for the first time, solve it and
      # store its result in a dictionary
      if key not in lookup:
   
          # Case 1. Include the current item `A[n]` in the subset and recur
          # for the remaining items `n-1` with the decreased total `k-A[n]`
          include = subsetSum(A, n - 1, k - A[n], lookup)
   
          # Case 2. Exclude the current item `A[n]` from the subset and recur for
          # the remaining items `n-1`
          exclude = subsetSum(A, n - 1, k, lookup)
   
          # assign true if we get subset by including or excluding the current item
          lookup[key] = include or exclude
   
      # return solution to the current subproblem
      return lookup[key]
   
   
  if __name__ == '__main__':
   
      # Input: a set of items and a sum
      A = [7, 3, 2, 5, 8]
      k = 14
   
      # create a dictionary to store solutions to subproblems
      lookup = {}
   
      if subsetSum(A, len(A) - 1, k, lookup):
          print('Subsequence with the given sum exists')
      else:
          print('Subsequence with the given sum does not exist')
  </code></pre>
  <p>It is said that the complexity of this algorithm is O(n * sum), but I can't understand how or why;
  can someone help me? Could be a wordy explanation or a recurrence relation, anything is fine</p>