LeetCode 494: Target Sum — Step-by-Step Visual Trace

#leetcode #algorithms #python #dynamicprogramming

Medium — Dynamic Programming | Array | Backtracking | Math

The Problem

Given an integer array nums and a target integer, find the number of ways to assign '+' or '-' signs to each element so that the sum equals the target.

Approach

Transform the problem into a subset sum problem by finding how many ways we can select elements to form a positive subset. Use dynamic programming with a 1D array where dp[i] represents the number of ways to achieve sum i.

Time: O(n * target) · Space: O(target)

Code

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        # Calculate the sum of all elements in the input array 'nums'.
        total_sum = sum(nums)

        # If the total sum is less than the target sum 'S', it's not possible to reach 'S'.
        if (total_sum + S) % 2 != 0 or total_sum < abs(S):
            return 0

        # Calculate the target sum for positive signs. (total_sum + S) / 2
        target = (total_sum + S) // 2

        # Initialize a 1D array 'dp' to store the number of ways to reach each sum from 0 to 'target'.
        dp = [0] * (target + 1)

        # There is one way to reach a sum of 0 (by not selecting any element).
        dp[0] = 1

        # Iterate through each element in the input array 'nums'.
        for num in nums:
            # Update the 'dp' array for each sum from 'target' to 'num'.
            for i in range(target, num - 1, -1):
                dp[i] += dp[i - num]

        # The 'dp[target]' contains the number of ways to reach the target sum 'S'.
        return dp[target]