Simple recursive solution with two optimizations:

- buffer any intermediate results
- terminate early if the sum out of the range of possible sums in the array

```
class Solution(object):
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
n = len(nums)
max_pos = sum(nums)
dic = {}
def rec(start, s,max_pos):
if start == n:
return 1 if s ==0 else 0
if s >max_pos or s<-max_pos:
return 0
if (start,s) in dic:
return dic[(start,s)]
res = rec(start+1, s- nums[start], max_pos - nums[start]) + rec(start+1, s+nums[start],max_pos - nums[start])
dic[(start,s)] = res
return res
return rec(0,S,max_pos)
```