Leetcode-Medium 494. Target Sum

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.

public class Solution {
    int count = 0;
    public int findTargetSumWays(int[] nums, int S) {
        calculate(nums, 0, 0, S);
        return count;
    }
    public void calculate(int[] nums, int i, int sum, int S) {
        if (i == nums.length) {
            if (sum == S)
                count++;
        } else {
            calculate(nums, i + 1, sum + nums[i], S);
            calculate(nums, i + 1, sum - nums[i], S);
        }
    }
}

1、该问题求解数组中数字只和等于目标值的方案个数，每个数字的符号可以为正或负(减整数等于加负数)。

2、该问题和矩阵链乘很相似，是典型的动态规划问题

3、举例说明: nums = {1,2,3,4,5}, target=3, 一种可行的方案是+1-2+3-4+5 = 3

     该方案中数组元素可以分为两组，一组是数字符号为正(P={1,3,5})，另一组数字符号为负(N={2,4})

     因此: sum(1,3,5) - sum(2,4) = target

              sum(1,3,5) - sum(2,4) + sum(1,3,5) + sum(2,4) = target + sum(1,3,5) + sum(2,4)

              2sum(1,3,5) = target + sum(1,3,5) + sum(2,4)

              2sum(P) = target + sum(nums)

              sum(P) = (target + sum(nums)) / 2

     由于target和sum(nums)是固定值，因此原始问题转化为求解nums中子集的和等于sum(P)的方案个数问题

class Solution(object):
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        if sum(nums) < S: return 0
        if (sum(nums) + S) & 1: return 0

        target = (sum(nums) + S) // 2
        dp = [0] * (target+1)
        dp[0] = 1

        for i in range(len(nums)):
            for val in range(target, nums[i]-1, -1):
                if dp[val-nums[i]]:
                    dp[val] += dp[val-nums[i]]
        return dp[-1]