LeetCode494：目标和

题目描述

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

代码
回溯

class Solution {
public:
    int count = 0;
    void backTracking(const vector<int>& nums, const int& target, int index, int sum) {
        if (index == nums.size()) {
            if(sum==target)
                count++;
        }
        else {
            backTracking(nums, target, index + 1, sum + nums[index]);
            backTracking(nums, target, index + 1, sum - nums[index]);
        }
    }

    int findTargetSumWays(vector<int>& nums, int target) {
        backTracking(nums, target, 0, 0);
        return count;
    }
};

动态规划

/*
   left是正数集合，right是负数集合

    left - right = target
    left + right = sum

    left = (sum+target) / 2
    right = (sum-target) / 2
    如果不能整除 直接return 0;

    将left = (sum+target)/2 看做是背包的容量
    看有多少种方法能将背包装满

    dp[j]： 装满容量为j的背包，有dp[j]种方法
    
    递推公式：已有  可以凑成的数量（以5为例）
                1   dp[4]种 凑成dp[5]
                2   dp[3]种 凑成dp[5]
                3   dp[2]种 凑成dp[5]
                4   dp[1]种 凑成dp[5]
                5   dp[0]种 凑成dp[5]
            dp[j]+=dp[j-nums[i]]

    初始化：dp[0] = 1;
    
    遍历顺序：
            for(int i=0;i=nums[i];j--)
                    dp[j]+= dp[j-nums[i]]
*/

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {

        int sum = 0;
        for (int a : nums) sum += a;

        if (abs(target)>sum || (sum + target) % 2 != 0) return 0;

        int left = (sum + target) / 2;
        vector<int> dp(left + 1, 0);
        dp[0] = 1;

        for(int i=0;i<nums.size();i++)
            for (int j = left; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        return dp[left];
        
    }
};