LeetCode 494. 目标和

约 5 分钟
文章信息 12 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 20-50 腾讯 字节 华为 微软 美团 百度 虾皮
标签
数组 动态规划 回溯

题目描述

✅ 494. 目标和

image-20260928200721557

image-20260928200721558

题意分析

给非负整数数组的每个位置选择一个正号或负号，使整个表达式的结果恰好等于 target，统计全部符号分配方案。每个位置都必须使用一次，可以全部取正，也可以全部取负。

数值相同的不同位置仍然独立选择；零前面的正号和负号也算两种符号方案。返回的是方案数，不是能否达到目标，也不能按最终数值表达式去重。

解法：转化为 0/1 背包计数

核心思路

[!blue]

把选正号的位置分为一组，数值和记为 P；选负号的位置分为另一组，数值和记为 N。有 P - N = target，又因为所有元素恰好分进两组，P + N = sum，所以 P = (sum + target) / 2。

数组都是非负数，任何符号方案的结果只能落在 [-sum, sum] 内；同时 P 必须是整数，因此先检查目标范围以及 sum + target 的奇偶性。不满足就无解，满足后问题变成：有多少种下标子集，其元素和恰好为 P。选入子集的位置取正号，其余取负号，子集与符号方案一一对应。

用 dp[j] 表示处理过的元素中，选出和恰好为 j 的方案数。初始 dp[0] = 1，表示一个元素都没选的空子集，其余为零。加入数值 num 时，不选它的旧方案仍保留；选它的方案来自之前和为 j - num 的状态，所以执行 dp[j] += dp[j - num]。

每个位置只能选择一次，因此容量从大到小更新。num > 0 时，较小容量 j - num 还没被本轮改过，读到的是不含当前元素的旧状态；正序则可能重复利用本轮刚加入的元素。

num == 0 时也不能跳过：选择这个零或不选择它，和不变但下标子集不同，恰好对应正零与负零两种符号。转移变为 dp[j] += dp[j]，将已有方案翻倍一次，正好符合要求。

解题步骤

  1. 求数组总和 sum，目标超出 [-sum, sum] 或 sum + target 为奇数时返回零。
  2. 令 capacity = (sum + target) / 2，创建容量从零到 capacity 的计数数组，只初始化 dp[0] = 1。
  3. 按数组位置逐个处理 num，从 capacity 倒序到 num 更新 dp[j] += dp[j - num]。
  4. 数值为零时仍执行同样更新，包含容量零在内的每个状态都翻倍一次。
  5. 返回 dp[capacity]，即对应目标的符号方案总数。

代码实现

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;

        for (int num : nums) {
            sum += num;
        }

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

        // 正号子集的和由总和与目标之和的一半确定。
        int capacity = (sum + target) / 2;
        int[] dp = new int[capacity + 1];

        dp[0] = 1;

        for (int num : nums) {
            // 倒序保证每次出现只选择一次，零元素会让当前计数加倍。
            for (int j = capacity; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }

        return dp[capacity];
    }
}

func findTargetSumWays(nums []int, target int) int {
    sum := 0
    for _, num := range nums {
        sum += num
    }
    if target > sum || target < -sum || (sum+target)%2 != 0 {
        return 0
    }

    // 正号子集的和由总和与目标之和的一半确定。
    capacity := (sum + target) / 2
    dp := make([]int, capacity+1)
    dp[0] = 1
    for _, num := range nums {
        // 倒序保证每次出现只选择一次，零元素会让当前计数加倍。
        for j := capacity; j >= num; j-- {
            dp[j] += dp[j-num]
        }
    }
    return dp[capacity]
}

复杂度分析

  • 时间复杂度：$O(n(P+1))$，P = (sum + target) / 2。每个元素最多更新从零到 P 的 P + 1 个状态；写成 P + 1 也覆盖目标容量为零的情况。
  • 空间复杂度：$O(P+1)$，只保存一行子集和计数。

关键点总结

[!green]

  • 正负分组推导出子集和容量，且每个下标子集唯一决定一组符号。
  • 状态表示恰好凑出某个和的数量，空选择提供唯一初始计数。
  • 倒序更新保留上一轮来源，保证每个位置只使用一次。
  • 零不改变和，却增加符号选择，统一转移自然完成计数翻倍。

易错点总结

[!yellow]

  • 只检查目标大于总和，漏掉过小的负目标，可能得到负容量；上下界都必须检查。
  • 不判断奇偶就进行整数除法，会把本来不是整数的正号组和截断成一个错误容量。
  • 容量正序更新，当前元素可能在同一轮被反复使用，变成允许重复选择的背包。
  • 将 dp[0] 设为零，所有计数都失去起始来源，之后不会产生任何方案。
  • 跳过零或去重相同数值，丢掉不同位置、不同符号对应的独立选择。
  • 把状态改成只表示可达的布尔值，无法得到题目要求的方案数量。

相似题目

题目 难度 关联与区别
416. 分割等和子集 中等 同样将问题转成子集和，本题需要方案数量而不是可达布尔值。
518. 零钱兑换 II 中等 同样做容量计数，原题硬币可重复使用，本题每个下标只选择一次，更新方向不同。
1049. 最后一块石头的重量 II 中等 用容量动态规划表示可达和或组合数；本题将正负分配转为指定和子集计数，该题尽量把总重量划分得接近一半。
474. 一和零 中等 用容量动态规划表示可达和或组合数；本题将正负分配转为指定和子集计数，该题把容量扩展为零和一的两维预算。
补充题 129. 目标和非空子序列计数 中等 都用子集和计数 DP，倒序更新容量避免重复使用元素；补充题还需排除空选择。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/25056900
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！