494. 目标和

给你一个非负整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

目标和（Target Sum），是一道经典的 动态规划 问题，也可以转化为 0-1 背包问题。

🧠 问题理解

给定一个非负整数数组 nums 和一个整数 target，对每个数字前加 + 或 -，使得总和等于 target。问有多少种不同的表达式可以做到这一点。

🔍 关键转化：数学建模

设：

• 所有加号的数字之和为 P
• 所有减号的数字之和为 N
• 数组总和为 sum = P + N

那么表达式的值为： P - N = target

又因为：P + N = sum

联立得：2P = target + sum，从而P = (target + sum) / 2

所以问题转化为：

在 nums 中选出若干数，使其和为 P，问有多少种选法？

这就是一个 0-1 背包计数问题！

⚠️ 注意前提条件：

1. target + sum 必须是非负且为偶数，否则无解。
2. P 必须 ≥ 0

✅ 动态规划解法（0-1 背包计数）

定义：

• dp[j] 表示和为 j 的子集个数

初始化：

• dp[0] = 1（和为 0 有一种方法：什么都不选）

状态转移（从后往前遍历背包容量，避免重复使用）：

for (int num : nums) {
    for (int j = P; j >= num; j--) {
        dp[j] += dp[j - num];
    }
}

💡 Java 实现

import java.util.Arrays;

public class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        
        // 检查是否可能达成 target
        if (Math.abs(target) > sum) return 0;
        if ((target + sum) % 2 != 0) return 0;
        
        int P = (target + sum) / 2;
        if (P < 0) return 0; // 因为 nums 非负，P 不能为负
        
        int[] dp = new int[P + 1];
        dp[0] = 1;
        
        for (int num : nums) {
            for (int j = P; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        
        return dp[P];
    }
}

⏱️ 复杂度分析

• 时间复杂度：O(n × P)，其中 n 是 nums 长度，P = (sum + target) / 2
• 空间复杂度：O(P)

注：若 target 为负，由于我们用 P = (sum + target)/2，只要 sum + target >= 0 且为偶数即可，代码中已处理。

---

✅ 总结

• 将“加减符号”问题转化为 子集和为 P 的组合数
• 利用 0-1 背包的计数型 DP 高效求解
• 注意边界条件：奇偶性、负数、绝对值超限等