This is a pretty easy problem. Just do DFS and try both "+" and "-" at every position. Easy version of `Expression Add Operators`

https://leetcode.com/problems/expression-add-operators/

```
public class Solution {
int result = 0;
public int findTargetSumWays(int[] nums, int S) {
if (nums == null || nums.length == 0) return result;
helper(nums, S, 0, 0);
return result;
}
public void helper(int[] nums, int target, int pos, long eval){
if (pos == nums.length) {
if (target == eval) result++;
return;
}
helper(nums, target, pos + 1, eval + nums[pos]);
helper(nums, target, pos + 1, eval - nums[pos]);
}
}
```

Optimization: The idea is `If the sum of all elements left is smaller than absolute value of target, there will be no answer following the current path. Thus we can return.`

```
public class Solution {
int result = 0;
public int findTargetSumWays(int[] nums, int S) {
if(nums == null || nums.length == 0) return result;
int n = nums.length;
int[] sums = new int[n];
sums[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--)
sums[i] = sums[i + 1] + nums[i];
helper(nums, sums, S, 0);
return result;
}
public void helper(int[] nums, int[] sums, int target, int pos){
if(pos == nums.length){
if(target == 0) result++;
return;
}
if (sums[pos] < Math.abs(target)) return;
helper(nums, sums, target + nums[pos], pos + 1);
helper(nums, sums, target - nums[pos], pos + 1);
}
}
```