> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/494-mu-biao-he.md).

# \[494]\[中等]\[动态规划]\[背包] 目标和

## 题目描述

[494. 目标和](https://leetcode-cn.com/problems/target-sum/)

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

```
输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：

-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

一共有5种方法让最终目标和为3。
```

提示：

* 数组非空，且长度不会超过 20 。
* 初始的数组的和不会超过 1000 。
* 保证返回的最终结果能被 32 位整数存下。

## 解题思路

这种题目都可以转换成将原数组拆分成两个数组, 使得一个数组之和恰好为X的题目. 因此是标准的01背包问题.

题目中物品就是原数组中的元素. 本题的背包限制, 即一个数组的和的值可以这样求:

假设所有元素和为sum，所有添加正号的元素的和为A，所有添加负号的元素和为B，则有sum = A + B 且 S = A - B，解方程得A = (sum + S)/2。即题目转换成：从数组中选取一些元素使和恰好为(sum + S) / 2.

由于本题是求方法数, 因此dp全部初始化为0, 只有dp\[0]初始化为1. 状态转移公式中的`max`也要变为`sum`.

```python
class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        total = sum(nums)
        if total < S or total < -S:
            return 0
        if (total + S) % 2:
            return 0

        target = (total + S) // 2
        dp = [0] * (target + 1)
        dp[0] = 1

        for i in range(len(nums)):
            for j in range(target, nums[i] - 1, -1):
                dp[j] = dp[j] + dp[j - nums[i]]
        return dp[-1]
```