Python intuitive DFS solution with memorization

  • 9

    At first I just remember the current index and current target, and for each index, either subtract the nums[i] from S or add it to S. But this got TLE, them I came up with this solution. Just store the intermediate result with (index, s) and this got accepted.

    class Solution(object):
        def findTargetSumWays(self, nums, S):
            :type nums: List[int]
            :type S: int
            :rtype: int
            def findTarget(i, s):
                if (i, s) not in cache:
                    r = 0
                    if i == len(nums):
                        if s == 0:
                            r = 1
                        r = findTarget(i+1, s-nums[i]) + findTarget(i+1, s+nums[i])
                    cache[(i, s)] = r
                return cache[(i, s)]
            cache = {}
            return findTarget(0, S)

Log in to reply

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