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

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 fr