Target Sum

Intuition

Split the numbers into a positive group with sum P and a negative group with sum N. Then P - N equals the target and P + N equals the total, so adding those equations gives P = (total + target) / 2. If total + target is negative or odd, no valid assignment exists, so we return 0. Otherwise the problem becomes counting how many subsets of the numbers add up to exactly P, which is a 0/1 knapsack counting problem. We accumulate counts with dp[s] += dp[s - num], iterating sums downward so each number is used at most once.

Algorithm walkthrough

1. 1Compute total. If (total + target) is negative or odd, return 0 because P would not be a non-negative integer.
2. 2Set P = (total + target) / 2, the required sum of the positively signed subset.
3. 3Create a counting array dp of size P + 1 with dp[0] = 1, representing one way to reach a sum of zero (choose nothing).
4. 4For each number, iterate s from P down to the number and add dp[s - num] into dp[s], counting subsets that include the current number.
5. 5Return dp[P], the total number of subsets that sum to P and therefore the number of valid sign assignments.

Implementation

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        if (total + target) < 0 or (total + target) % 2 != 0:
            return 0
        p = (total + target) // 2
        dp = [0] * (p + 1)
        dp[0] = 1
        for num in nums:
            for s in range(p, num - 1, -1):
                dp[s] += dp[s - num]
        return dp[p]