# Python simple DFS solution [705 ms]

• 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)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.