代码随想录——目标和（Leetcode494）不会

题目链接

0-1背包

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        // 此时无方案
        if(Math.abs(target) > sum){
            return 0;
        }
        // 此时无方案
        if((sum + target) % 2 == 1){
            return 0;
        }
        int bagSize = (sum + target) / 2;
        int[] dp = new int[bagSize + 1];
        // dp初始化
        dp[0] = 1;
        for(int i = 0; i < nums.length; i++){
            for(int j = bagSize; j >= nums[i]; j--){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
}

本题目标：如何使表达式结果为target
left - right = target
left + right = sum
left = (target + sum) / 2
target、sum固定，left可以求出来
本题思路：在集合nums中找出和为left的组合

转化为0-1背包问题：
加法总和为x，减法总和为sum - x，最终目标为x = (target + sum) / 2
递推公式（组合类问题公式）：dp[j] += dp[j - nums[i]]