image.png

解法

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum =  0;
        for (int num : nums) {
            sum += num;
        }
        if (target > sum) {
            return 0;
        }
        if ((sum + target) % 2 == 1) {
            return 0;
        }

        // 转换为求sum和target和的一半
        int count = (sum + target) / 2;
        if (count < 0) {
            return 0;
        }
        int[] dp = new int[count + 1];
        // 初始化
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = count; j >= nums[i]; j--) {
                // 组合数目，加上不取当前的时候有几个
                dp[j] += dp[j - nums[i]];        
            }
        }
        return dp[count];
    }
}