Question 494. Target Sum

Link:

My Code:

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        LargestSum = sum(nums)
        SmallestSum = -LargestSum
        if LargestSum<S or SmallestSum>S:
            return 0
        else:
            ResultMat = []
            for l in range(len(nums)):
                List = [0]*(LargestSum*2+1)
                ResultMat.append(List)
            ResultMat[0][nums[0]] = ResultMat[0][nums[0]]+1
            ResultMat[0][-nums[0]] = ResultMat[0][-nums[0]]+1
            for i in range(1,len(nums)):
                for j in range(-LargestSum,LargestSum+1,1):
                    Index1 = j-nums[i]
                    Index2 = j+nums[i]
                    if Index1 <-LargestSum:
                        Value1 =0
                    else:
                        Value1 = ResultMat[i-1][Index1]
                    if Index2> LargestSum:
                        Value2 = 0
                    else:
                        Value2 = ResultMat[i-1][Index2]
                    Value = Value1+Value2
                    ResultMat[i][j] = Value
            return ResultMat[len(nums)-1][S]

Explanation: I use a two dimension matrix to store the data. The row is the ith element of the original list, the column is the Sum j and the value stored in the matrix[i][j] is the total number that can achieve value j at the ith index. Then to for i+1 Index, the only way to achieve the sum j is that we have achieved j+ nums[i+1] or j-nums[i+1] at the index i. Hence we just sum these two values together to get the total number that can achieve j at i+1.