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

题目链接：494. 目标和

要在数组中通过加减元素得到目标和，记加的元素和为x，减的元素和为y，即x-y=target

又因为x y=sum，两式相加，可以求得x=（target sum）/2，即题目变成能不能在元素里面找到一个组合的和为x，即0-1背包问题，基本同【LeetCode】【0-1背包】分割等和子集-CSDN博客

dp[i]变成存在子集和为i的个数

注意如果target sum不是偶数或者target的绝对值大于sum都是没有的

代码语言：javascript复制

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];
    }
};

leetcode sum target 博客 数组

0 人点赞