【LeetCode】【0-1背包】目标和

class Solution {
public:
    int findTargetSumWays(vector<int> &nums, int target) {
        int sum = 0;
        for (auto &num: nums)sum += num;
        if (sum + target & 1 || abs(target) > sum)return 0;
        int x = (sum + target) / 2;
        vector<int> dp(x + 1);
        dp[0] = 1;
        for (auto &num: nums)
            for (int i = x; i >= num; --i)
                dp[i] += dp[i - num];
        return dp[x];
    }
};