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

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

**示例1**
```
输入: 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位整数存下。

## 代码(dfs)
```C++
class Solution {
public:
    int way = 0;
    int target = 0;
    vector<int> data;
    int findTargetSumWays(vector<int>& nums, int S) {
        data = vector<int>(1,0);
        data.insert(data.end(),nums.begin(),nums.end());
        target = S;
        findTargetSumWays(1, 0);
        return way;
    }
    void findTargetSumWays(int index, int current) {
        if(index < data.size()){
            findTargetSumWays(index+1, current+data[index]);
            findTargetSumWays(index+1, current-data[index]);
        }else{
            if(current == target){
                way++;
            }
        }
    }
};
```

## 代码(dp)
```C++
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = accumulate(nums.begin(),nums.end(),0);
        if(sum < S || (S + sum) % 2 == 1){
            return 0;
        }
        int p = (S + sum) / 2;
        vector<int> dp(p+1,0);
        dp[0] = 1;
        for(int i = 0;i < nums.size();i++){
            for(int j = p;j >= nums[i];j--){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[p];
    }

};
```

## 思路

### 解法1
这题很自然的想法就是dfs暴力计算，写起来也很容易。可以在数组前面添加一个0来满足第一个数字可以为正负数，然后也需注意dfs深度与原数组长度相同，需要判断下，但是这样的复杂度比较高。

### 解法2
优雅一些的做法是使用dp，具体思路如下图所示。

![图片](/static/494_1.png)
![图片](/static/494_2.png)
![图片](/static/494_3.png)
{'avg_line_length': 19.655172413793103, 'max_line_length': 91, 'alphanum_fraction': 0.519298245614035, 'licenses': ['MIT'], 'repository_name': 'LebronAl/myLeetcodeDailyRecord', 'path': '494_目标和.md', 'size': 2262, 'lang': 'Markdown'}