Target Sum
You are given an array nums and an integer target.
For every value in nums, choose exactly one sign: + or -, then evaluate the full expression.
Return how many different sign assignments produce a final value equal to target.
A different assignment means at least one position uses a different sign.
Examples
Input: [[1,1,1,1,1],3]
Output: 5
Input: [[1],1]
Output: 1
Hints
**Hint 1**: Consider the problem as a subset sum problem where you need to partition the array into two subsets such that their difference equals the target. Think about how the sum of one subset relates to the sum of the other.
**Hint 2**: Let `S` be the sum of all elements in `nums`. If `S < target` or `(S + target)` is odd, return 0 immediately since no valid assignment exists. Otherwise, reduce the problem to finding the number of subsets that sum to `(S + target) / 2`.
**Hint 3**: Use dynamic programming to count the number of ways to achieve the target sum. Define a DP array where `dp[i][j]` represents the number of ways to achieve sum `j` using the first `i` elements. Optimize space by using a 1D array and iterating backwards.
Target Sum
You are given an array `nums` and an integer `target`.