https://leetcode.com/problems/target-sum/

Q. You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols+and-. For each integer, you should choose one from+and-as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input:
 nums is [1, 1, 1, 1, 1], S is 3. 

Output:
 5

Explanation:


-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

Catch: Convert to subset sum problem (recall DP states)

// choosing - sign for 4 is like excluding 8 in the subset

Code

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        long s = (long)S;
        for (int i = 0; i < nums.length; i++) {
            s += nums[i];
            nums[i] += nums[i];
        }
        if (s > 2000) {
            return 0;
        }
        int[][] dp = new int[(int)s + 1][nums.length + 1];
        dp[0][0] = 1;
        for (int i = 0; i <= s; i++) {
            for (int j = 1; j <= nums.length; j++) {
                dp[i][j] = dp[i][j - 1];
                if (nums[j - 1] <= i) {
                    dp[i][j] += dp[i - nums[j - 1]][j - 1];
                }
            }
        }
        return dp[(int)s][nums.length];
    }
}