so based on the notes this is a bin tree with height <=20：

for a given input **[1,2]**, it means bin tree

**[0, -1, 1, -2, 2, -2, 2]**

then i wrote a simple DFS as below, but I got a TLE.

then i found some intermediate results can be cached...

so the DFS with DP code got AC.

```
class Solution(object):
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
# TLE
# def dfs(depth, sum_all, ans):
# if depth >= len(nums): # now we are in the bottom level
# if sum_all == S:
# ans[0] += 1
# return
# dfs(depth + 1, sum_all - nums[depth], ans)
# dfs(depth + 1, sum_all + nums[depth], ans)
#
# sum_all = 0
# ans = [0]
# dfs(0, sum_all, ans)
# return ans[0]
# then i found some intermediate results can be cached...
# DP, by cache the intermediate results
def dfs(depth, sum_all=0, num_ways_cache={}):
if depth >= len(nums): # now we are in the bottom level
# print depth, sum_all
if sum_all == S:
return 1
return 0
if (depth, sum_all) in num_ways_cache:
return num_ways_cache[(depth, sum_all)]
num_of_ways = dfs(depth + 1, sum_all - nums[depth], num_ways_cache) + \
dfs(depth + 1, sum_all + nums[depth], num_ways_cache)
num_ways_cache[(depth, sum_all)] = num_of_ways
return num_of_ways
return dfs(0)
```