LeetCode 494. 目标和

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 494. 目标和

思路分析

这个问题本质上是一个“背包问题”的变种问题，类似于“和为某个目标的子集和”问题。

假设数组中有一些数加上去，另一些数减去去。假设加上去的数的和是 P，减去去的数的和是 Q，那么就有：

P - Q = S P + Q = sum(nums)

由此我们可以推导出：P = (sum(nums) + S) / 2

也就是说，问题转化成了如何从数组 nums 中找到一些数，使得它们的和为 P。这个问题变成了一个经典的“背包问题”，可以通过动态规划来求解。

参考代码

func findTargetSumWays(nums []int, S int) int {
	sum := 0
	for _, num := range nums {
		sum += num
	}

	if (sum+S)%2 != 0 {
		return 0
	}

	target := (sum + S) / 2
	if target < 0 {
		return 0
	}

	dp := make([]int, target+1)
	dp[0] = 1

	for _, num := range nums {
		for i := target; i >= num; i-- {
			dp[i] += dp[i-num]
		}
	}

	return dp[target]
}

➡️ 点击查看 Java 题解

write your code here

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/25056900