> For the complete documentation index, see [llms.txt](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/494.target-sum.md).
# 0494. 目标和
### 题目地址(494. 目标和)
### 题目描述
```
给定一个非负整数数组，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 位整数存下。
```
### 前置知识
* 动态规划
### 公司
* 阿里
* 腾讯
* 百度
* 字节
### 思路
题目是给定一个数组，让你在数字前面添加 `+`或者`-`，使其和等于 target.
暴力法的时间复杂度是指数级别的，因此我们不予考虑。我们需要换种思路.
我们将最终的结果分成两组，一组是我们添加了`+`的，一组是我们添加了`-`的。
如上图，问题转化为如何求其中一组，我们不妨求前面标`+`的一组
> 如果求出一组，另一组实际就已知了，即总集和这一组的差集。
通过进一步分析，我们得到了这样的关系：
因此问题转化为，求解`sumCount(nums, target)`,即 nums 数组中能够组成 target 的总数一共有多少种，这是一道我们之前做过的题目，使用动态规划可以解决。
### 关键点解析
* 对元素进行分组，分组的依据是符号， 是`+` 或者 `-`
* 通过数学公式推导可以简化我们的求解过程，这需要一点`数学知识和数学意识`
### 代码
```js
/*
* @lc app=leetcode id=494 lang=javascript
*
* [494] Target Sum
*
*/
// 这个是我们熟悉的问题了
// 我们这里需要求解的是nums里面有多少种可以组成target的方式
var sumCount = function (nums, target) {
// 这里通过观察，我们没必要使用二维数组去存储这些计算结果
// 使用一维数组可以有效节省空间
const dp = Array(target + 1).fill(0);
dp[0] = 1;
for (let i = 0; i < nums.length; i++) {
for (let j = target; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[target];
};
const add = (nums) => nums.reduce((a, b) => (a += b), 0);
/**
* @param {number[]} nums
* @param {number} S
* @return {number}
*/
var findTargetSumWays = function (nums, S) {
const sum = add(nums);
if (sum < S) return 0;
if ((S + sum) % 2 === 1) return 0;
return sumCount(nums, (S + sum) >> 1);
};
```
**复杂度分析**
* 时间复杂度：$O(N \* target)$
* 空间复杂度：$O(target)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
### 扩展
如果这道题目并没有限定所有的元素以及 target 都是正数怎么办？