# Target Sum

• The animation is not very intuitive. Can someone explain the 2D DP solution?

• It's not good to use the constrain such as 1000, 2000

• It's may be good for online test but not good for coding interview or in practice.

• for approach 2, the space complexity should be O(nl) due to "memo"

• The line of int count = 0 in the code of Approach 2 is useless.

• 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];
}
}

• If the target S is -10000, the approach 2 throw array outbound error. It should test whether S > 1000 || S < -1000, if so, return 0.

• For Approach #1, you can add an easy prune: abort an iteration if `sum` get too big or too small. This is possible because each entry is non-negative.

• My similar solution to approach 3. Although I defined the second index of the table `dp` as `offset from target sum`, rather than `target sum` itself. This ensures that large `S` 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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.