494. Target Sum - cocoder39/coco39_LC GitHub Wiki

494. Target Sum

l * n subproblems and it takes O(1) time complexity to solve a problem with its subproblem solutions so total time complexity is O(l * n)

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        memo = collections.defaultdict(dict)
        
        def helper(start_idx, target):
            if start_idx == len(nums):
                return 1 if target == 0 else 0
        
            if start_idx in memo and target in memo[start_idx]:
                return memo[start_idx][target]
            
            memo[start_idx][target] = helper(start_idx+1, target-nums[start_idx]) + helper(start_idx+1, target+nums[start_idx])
            
            return memo[start_idx][target]
        
        return helper(0, S)

DP solution

dp[i][j] refers to the number of assignments which can lead to a sum of j upto the i-th index

dp[i][sum + nums[i]] += dp[i - 1][sum];
dp[i][sum - nums[i]] += dp[i - 1][sum];