494. Target Sum | 背包问题 | 动态规划

问题描述

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.

Note:
The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

思路

本题可以理解为：找一个正的subset和一个负的subset，使他们两部分的和为target。

用P表示正集合，N表示负集合
如果给定 nums = [1,2,3,4,5] , target = 3
那么其中一个解为 +1-2+3-4+5 = 3
也就是说P = [1,3,5] , N = [2,4]

对这道题进行转换：

sum(P) - sum(N) = target
	sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
						   2 * sum(P) = target + sum(nums)

问题也就转换成：

找到一个subset P，使得 sum(P) = (target + sum(nums)) / 2

这个式子还说明，找出的P集合的和一定是偶数，这样可以快速去掉一部分不满足和为偶数的结果。 (Thanks to @BrunoDeNadaiSarnaglia for the suggestion)

之后的做法和416. Partition Equal Subset Sum类似

代码

class Solution {
    public int findTargetSumWays(int[] nums, int s) {
    	// 数组求和
        int sum = 0;
        for(int n : nums) sum += n;
        // sum比s小或者s+sum不是偶数，都返回0
        if(sum<s || (s + sum)%2!=0) return 0;
        return subsetSum(nums, (s + sum) >>> 1); 
    }
    public int subsetSum(int[] nums, int s) {
        int[] dp = new int[s + 1]; 
        dp[0] = 1;
        for (int n : nums)
            for (int i = s; i >= n; i--)
                dp[i] += dp[i - n]; 
        return dp[s];
    }
}

Beats 99.40%