Python simple DFS solution [705 ms]


  • 0

    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)
    

Log in to reply
 

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