题目描述

原题链接：494. 目标和

解题思路

（1）回溯法

本题的特点是nums中每个元素只能使用一次，分别试探加上nums[index]和减去nums[index]，然后递归的遍历下一个元素index + 1。

class Solution {
public:
    int res = 0;
    void backtracking(vector<int>& nums, int target, int index) {
        if(index == nums.size()) {
            if(target == 0)         res++;
            return ;
        }

        backtracking(nums, target - nums[index], index + 1);
        backtracking(nums, target + nums[index], index + 1);
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        backtracking(nums, target, 0);
        return res;
    }
};

（2）动态规划

本题中的数都为非负数，目标要求是选取组成正数的数与负数的数，让其和为target，因此我们可以将这个题中的数划分为两个集合，一个是要组成正数的集合，设容量为pos，一个是要组成负数的集合，设容量为neg。

由题中要求可得pos - neg = target，pos + neg = sum，联立两式，可得2 * pos = target + sum，因此我们就可以进行第一个判定，当target + sum不为偶数时，可知一定不能组合出target直接返回false即可。当为偶数时，我们要找到可以组成pos（pos = (target + sum) / 2）的组合。问题就可以转变为，当背包容量为pos时，选取nums里的数，有多少种组合方式可填满背包。

1）二维数组

• 动态规划五步曲：

（1）dp[i][j]含义： 当背包容量为j时，填满j可到达方案总数是多少。

（2）递推公式： $dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]]$，到达dp[i][j]的方案来源于不选i时的方案与选i时的方案之和。

（3）dp数组初始化： 由于要求的时填满j的情况，因此让dp[0][0] = 1，表示容量为0时，一个都不放为一种情况。而其余的规定为dp[i][0] = - ∞（填满时为负无穷，只要求填充不要求填满则为0。因为已经经过上述求余的判定，所以当前一定可以填满）

（4）遍历顺序： 从上到下，从左到右。

（5）举例：（省略）

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size(), sumNums = 0;
        for(int i = 0; i < n; i++)          sumNums += nums[i];
        if(abs(target) > sumNums || (target + sumNums) % 2 != 0)            return 0;

        int pos = (sumNums + target) / 2;
        // 初始化要注意 
        vector<vector<int>> dp(n + 1, vector<int>(pos + 1));
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++)             dp[i][0] = INT_MIN;
        
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= pos; j++) {
                if(nums[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
                }                     
            }
        }

        return dp[n][pos];
    }
};  

2）滚动数组

• 动态规划五步曲：

（1）dp[j]含义： 装满背包容量为j的方式个数。

（2）递推公式： dp[j] += dp[j - nums[i]]，装入nums[i]之前，容量为j - nums[i]时的方式个数dp[j - nums[i]]，再加上装入nums[i]之后，容量为j时之前的方式个数dp[j]，进而得到背包容量为j时，总的方式个数。

（3）dp数组初始化： dp[0] = 1，容量为0时，仅有一种方式可以成立，即选择数字0。

（4）遍历顺序： 先物品、再背包，内层按从大到小遍历的滚动数组。

（5）举例：

输入： nums: [1, 1, 1, 1, 1], S: 3
此时，正数最大为4，里面只有1，因此dp[j]长度为4。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sumNums = 0;
        for(int i = 0; i < nums.size(); i++)                    sumNums += nums[i];
        // target超过总和或者不满足pos为偶数的情况，直接返回0
        if(abs(target) > sumNums || (sumNums + target) % 2 != 0)     return 0;

        int dp[10001] = {0};
        dp[0] = 1;
        int pos = (sumNums + target) / 2;
        for(int i = 0; i < nums.size(); i++) {
            for(int j = pos; j >= nums[i]; j--) {
                // 组合情况要累计
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[pos];

    }
};

参考文章：494. 目标和、目标和、目标和（详细C++代码动态规划详细思路分析）