Another Python solution: recusion + memoization (6 lines function)


  • 0
    H
    class Solution(object):
        def findTargetSumWays(self, nums, S):
            def brute_force(i, my_sum, cache={}):
                if (i, my_sum) not in cache:
                    if i == len(nums):
                        cache[(i, my_sum)] = 1 if my_sum == S else 0
                    else:
                        cache[(i, my_sum)] = brute_force(i + 1, my_sum + nums[i]) + brute_force(i + 1, my_sum - nums[i])
                return cache[(i, my_sum)]
    
            return brute_force(0, 0)

Log in to reply
 

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