**Key Observation:**

- Note that any
`x`

and`-x`

must be both odd or even, so there is no solution if`sum`

of array`a[]`

and target sum`s`

are different in`%2`

. (e.g.,`vector<int> a(20,1), s = 5`

) - Any zero entry
`a[i]`

does not contribute to sum, so it can be removed from array with a factor of`2`

in counting because`+0 = -0`

. - We can simply consider array
`a`

with all*positive*numbers. Then it is obvious that- if
`abs(s) > sum`

, there is no solution; (e.g.,`vector<int> a(20,1), s = 21`

) - if
`abs(s) = sum`

, there is only one solution, i.e., all`+`

or all`-`

signs. (e.g.,`vector<int> a(20,1), s = 20`

)

- if

With these early termination conditions, combined with the following recursion:

`m[i][s] = m[i-1][s-a[i]] + m[i-1][s+a[i]]`

, (`m[i][s] = findTargetSumWays(a[0:i],s)`

)

we have the following DFS code:

```
int findTargetSumWays(vector<int>& a, int s) {
int sum = 0; for (int x:a) if(x) pos.push_back(x), sum += x; // set pos and sum
m.resize(pos.size());
return (s%2 != sum%2)? 0 : pow(2,a.size()-pos.size())*(pos.empty()? 1 : dfs(pos.size()-1, s, sum));
}
int dfs(int i, int s, int sum) {
return m[i].count(s)? m[i][s] : m[i][s] =
(!i||abs(s)>=sum)? (abs(s)==sum) : dfs(i-1,s-pos[i],sum-pos[i])+dfs(i-1,s+pos[i],sum-pos[i]);
}
vector<unordered_map<int,int>> m; // m[i][s] = findTargetSumWays(pos[0:i],s)
vector<int> pos; // positive numbers in a
```