494. 目标和

力扣链接(中等)：https://leetcode.cn/problems/target-sum

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

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

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

个人题解

动态规划（滚动数组）

1. dp[j] 表示装满容量为 j 的背包有 dp[j] 种方法；
2. 递推公式：dp[j] += dp[j - nums[i]]，推导见下一部分；
3. 初始化 dp[0] = 1，即装满容量为 0 的背包有 1 种方法，因为该背包没有容量，天然是满的；
4. 遍历顺序见 416. 分割等和子集，有详细说明；
5. 手动推导 dp 数组无误。

组合类问题的 dp 递推公式

回到本题，不妨将 nums[i] 作为 weight[i] 那么有 dp[3] = dp[0] + dp[1] + dp[2]。

因为要装满容量为 3 的背包，无非有三种情况：

1. nums[i] = 1 时，有 dp[2] 种办法装满背包。因为由 dp 数组的定义知，装满容量为 2 的背包有 dp[2] 种方法，此时再把当前 nums[i] 装入背包，不就装满容量为 3 的背包了吗 ；
2. 同理，nums[i] = 2 时，有 dp[1] 种办法装满背包；
3. nums[i] = 3 时，有 dp[0] 种办法装满背包。

故装满容量为 3 的背包有 dp[3] = dp[0] + dp[1] + dp[2] 种方法，以此类推，得到通用递推公式：dp[j] += dp[j - nums[i]]。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(int i = 0; i < nums.size(); i++) sum += nums[i];

        // 处理无法凑出目标和的情况
        if(abs(target) > sum) return 0;
        if((target + sum) % 2) return 0;

        // 设 + 元素之和为 x，有 - 元素(绝对值)之和为 y = sum - x
        // 又 x - y = target，有 x = (target + sum) / 2
        // 将所有 + 元素放入容量为 + 元素之和的 01 背包
        int weight = (target + sum) >> 1;

        const int N = (1000 + 1000 >> 1) + 10;
        int dp[N] = {};
        dp[0] = 1;

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

        return dp[weight];
    }
};