Target Sum


Here is another solution, initially assign + to every number, then use dp to determine how many combination of flips from + to  are there to reach S.
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for (int n: nums) sum += n;
if (sum < S  (sum  S) % 2 == 1) return 0;
int target = (sum  S) / 2;
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 0; i < nums.length; i++) {
for (int j = target; j >= nums[i]; j) {
dp[j] += dp[j  nums[i]];
}
}
return dp[target];
}
}

My similar solution to approach 3. Although I defined the second index of the table
dp
asoffset from target sum
, rather thantarget sum
itself. This ensures that largeS
does not break the bounds.

@Chidong In the animation, in the 6th slide, last count values will be 1 2 3 4 3 2 1