494. Target Sum - LeetCode Solution

class Solution:
    def findTargetSumWays(self, arr: List[int], target: int) -> int:

        dppos = []


        for i in range(2001):
            k = []
            for i in range(len(arr) + 1):
                k.append(-1)

            dppos.append(k)






        def trav(s, j):
            if s == target and j == len(arr):
                return 1

            if j == len(arr):
                return 0



            if dppos[s + 1000][j] != -1:
                return dppos[s + 1000][j]
            dppos[s + 1000][j] = 0





            dppos[s + 1000][j]  += trav(s + arr[j], j+1)
            dppos[s + 1000][j] += trav(s - arr[j] , j+1)

            return dppos[s + 1000][j]


        return trav(0, 0)