class Solution {
    // 首先想到的是回溯，但是回溯的时间复杂度过大（2^n);
    // 想到背包问题：
    // 两个背包，一个放正数，一个放负数，
    // pos[i] - neg[i] = target;
    // pos[i] + neg[i] = sum;
    // pos[i] = (target + sum) / 2
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        //(target + sum)必须是偶数（否则 P 不是整数）
		//(target + sum)不能是负数（否则不可能）
        if ((target + sum) % 2 != 0 || (target + sum) < 0) {
            return 0;
        } 
        int[] pos = new int[(target + sum) / 2 + 1];
        pos[0]= 1; 
        //pos[i] 代表容量为i的背包有多少种方式填满
        for (int i = 0; i < nums.length; i++) {
            for (int j = (target + sum) / 2; j >= nums[i]; j--) {
                pos[j] += pos[j-nums[i]]; 
            }
        }
        return pos[(target + sum) / 2];
    }
}