算法：DP

01背包，注意有负体积背包，需要加上偏移量，偏移量就是数组能达到的最大和

假设数组和的范围是[-100, 100], 那么偏移量就是100，数组下标范围[0, 200]

复杂度

$O(NM)$

代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(target > sum || target < -sum) return 0;
        vector<vector<int>> f(n+1, vector<int>(2*sum + 1)); // f[i][j]: 考虑前i个物品，和为j的方案数
        f[0][0+sum] = 1;

        for(int i = 1; i <= n; i ++){
            for(int j = -sum; j <= sum; j ++){
                if(j - nums[i-1] >= -sum) f[i][j+sum] += f[i-1][j-nums[i-1]+sum];
                if(j + nums[i-1] <= sum) f[i][j+sum] += f[i-1][j+nums[i-1]+sum];
            }
        }

        return f[n][target+sum];
    }
};