vvrf / DSA.log

问题拆解

给每个数前面填 + 或 -，问有多少种填法使表达式等于 target。每个数两种选择，直接回溯枚举是 O(2ⁿ)——n <= 20 勉强能过，但这道题真正的价值在于一次漂亮的转化。

填符号其实是把数组分成两个子集：取正号的记作 P，取负号的记作 N。设 sum 为全体元素之和、p 为 P 的和，则负号部分的和是 sum - p，表达式的值就是 p - (sum - p) = target。解出：

p = (sum + target) / 2

于是原问题等价于：从数组中选出一个子集，使其和恰好为 p，有多少种选法。每个数选或不选、只用一次——0/1 背包的计数版。

这一步转化把“每个数二选一的符号问题”压成了“单侧子集的和”，搜索空间没变小，但结构从“枚举”变成了“计数背包”，复杂度从 2ⁿ 降到 n·p。

转化自带两个无解判定：sum + target 为奇数时 p 不是整数，无解；sum + target < 0（即 target < -sum）时 p 为负，而元素全部非负也无解。两种情况都直接返回 0。注意 target 本身可以是负数，判奇偶前先算 sum + target 而不是对 target 单独做假设。

转化为计数背包

dp[j] 表示凑出和 j 的方案数，转移是 dp[j] += dp[j - num]——求方案数用累加，而判可行性用或、求最值用 min/max，骨架相同。每个数只能用一次，所以一维数组照例倒序遍历。

public int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int x : nums) sum += x;
    // p = (sum + target) / 2 必须是非负整数
    if (sum + target < 0 || (sum + target) % 2 == 1) return 0;
    int p = (sum + target) / 2;
    int[] dp = new int[p + 1];
    dp[0] = 1; // 空集凑出 0，一种方案
    for (int num : nums) {
        for (int j = p; j >= num; j--) { // 0/1 背包倒序
            dp[j] += dp[j - num];
        }
    }
    return dp[p];
}

def findTargetSumWays(nums: list[int], target: int) -> int:
    total = sum(nums)
    # p = (total + target) / 2 必须是非负整数
    if total + target < 0 or (total + target) % 2 == 1:
        return 0
    p = (total + target) // 2
    dp = [0] * (p + 1)
    dp[0] = 1  # 空集凑出 0，一种方案
    for num in nums:
        for j in range(p, num - 1, -1):  # 0/1 背包倒序
            dp[j] += dp[j - num]
    return dp[p]

func findTargetSumWays(nums []int, target int) int {
    sum := 0
    for _, x := range nums {
        sum += x
    }
    // p = (sum + target) / 2 必须是非负整数
    if sum+target < 0 || (sum+target)%2 == 1 {
        return 0
    }
    p := (sum + target) / 2
    dp := make([]int, p+1)
    dp[0] = 1 // 空集凑出 0，一种方案
    for _, num := range nums {
        for j := p; j >= num; j-- { // 0/1 背包倒序
            dp[j] += dp[j-num]
        }
    }
    return dp[p]
}

pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
    let sum: i32 = nums.iter().sum();
    // p = (sum + target) / 2 必须是非负整数
    if sum + target < 0 || (sum + target) % 2 == 1 {
        return 0;
    }
    let p = ((sum + target) / 2) as usize;
    let mut dp = vec![0; p + 1];
    dp[0] = 1; // 空集凑出 0，一种方案
    for &num in &nums {
        let num = num as usize;
        for j in (num..=p).rev() { // 0/1 背包倒序
            dp[j] += dp[j - num];
        }
    }
    dp[p]
}

Python 的 % 对负数返回非负余数，Java、Go、Rust 则可能返回负余数，所以先判 sum + target < 0 再判奇偶，两个条件的顺序在这几门语言里都安全。另一个值得注意的点是数组里可以有 0：给 0 填正号或负号是两种不同的方案，转化后的背包会自动数对——0 参与倒序循环时 dp[j] += dp[j]，恰好把方案数翻倍，这也是不能随手把 0 过滤掉的原因。

回溯写法这里就不展开了：n <= 20 时逐位枚举正负号也能通过，适合作为验证 DP 结果的对拍基准。

复杂度

指标	复杂度	原因
时间	`O(n · p)`	每个数刷一遍长度为 p 的表，p = (sum+target)/2
空间	`O(p)`	一维计数数组

可以迁移的模式

“填正负号”“分两组”这类二选一问题，设一侧的和为未知数列方程，常能化归为子集和；
计数背包的转移是 dp[j] += dp[j - num]，与可行性版只差把“或”换成“加”，倒序规则不变；
转化得到的目标必须先做合法性检查（整除、非负），不合法直接返回，别带病进 DP。

这道题和第 416 题分割等和子集是同一个背包的两副面孔：那边问“能不能凑出 sum/2”，这边问“凑出 (sum+target)/2 有几种方式”。