494. Target Sum

This problem is equal to "find all ways to partition the array into two groups so that the difference of the sum of the two groups is Math.abs(S)". Assume the sum of the two subsets is s1 and s2 (s1 >= s2), the sum of the array is sum:

1. s1 + s2 = sum;
2. s1 - s2 = Math.abs(S)

So, s1 = (sum + Math.abs(S)) / 2. Now what we need to do is finding all subsets whose sum is s1, which is a typical 0-1 knapsack problem. We use dp[i][j] to denote the number of subsets whose sum is i for the first j elements in the array. Note that there could be zero in the array, dp[0][i] is no longer 0 as the normal knapsack problem, which means we need to process empty knapsack specially.

public int findTargetSumWays(int[] nums, int S) {
    int sum = 0;
    S = Math.abs(S);
    for(int i = 0; i < nums.length; i++)
        sum += nums[i];
    // Invalid S, just return 0
    if( S > sum || (sum + S) % 2 != 0 )
        return 0;

    int dp[][] = new int[(sum + S) / 2 + 1][nums.length + 1];
    dp[0][0] = 1;
    for(int i = 0; i < nums.length; i++) { // empty knapsack must be processed specially
        if( nums[i] == 0 )
            dp[0][i + 1] = dp[0][i] * 2;
        else
            dp[0][i + 1] = dp[0][i];
    }
    for(int i = 1; i < dp.length; i++) {
        for(int j = 0; j < nums.length; j++) {
            dp[i][j + 1] += dp[i][j];
            if( nums[j] <= i )
                dp[i][j + 1] += dp[i - nums[j]][j];
        }
    }
    return dp[(sum + S) / 2][nums.length];
}

The time of the solution above is 4ms, after optimizing the space by using one dimension dp array we can improve it to 2ms:

int dp[] = new int[(sum + S) / 2 + 1];
dp[0] = 1;
for(int i = 0; i < nums.length; i++) {
	for(int j = dp.length - 1; j >= nums[i]; j--) {
		dp[j] += dp[j - nums[i]];
	}
}
return dp[dp.length - 1];