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]
Watch It Run
👁 Watch the algorithm run step by step
👁 Watch the algorithm run step by step
Open interactive visualization
Try it yourself: Open TraceLit and step through every line.
Built with TraceLit — the visual algorithm tracer for LeetCode practice.
For further actions, you may consider blocking this person and/or reporting abuse
