# 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 都是正数怎么办？
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/494.target-sum.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.