Target Sum leetcode

Question

I am trying to solve this problem

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

My working solution that times out:

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        ways = 0 
        def dfs(index, s):
            nonlocal ways 
            if index == len(nums):
                if s == 0:
                    ways +=1 
            else:
                dfs(index+1, s-nums[index])
                dfs(index+1, s+nums[index])

        dfs(0, S)
        return ways

How to optimize this in terms of time complexity?

Please refrain from commenting that the method can exist as a function on its own; this is the template that leetcode uses and can't be changed.

https://leetcode.com/problems/target-sum/

Answer 1

Your solution computes all possible target sums that are obtained by distributing the signs \$+1\$ and \$-1\$ to the numbers. For an array with \$n\$ numbers that are \$2^n\$ combinations.

This is a typical case where dynamic programming is of advantage. Instead of searching for all combinations which lead to the target sum \$S\$, one computes the number of combinations leading to any target sum in a range.

The crucial hint here is

2. The sum of elements in the given array will not exceed 1000.

which means that only target sums between \$-1000\$ and \$1000\$ can be obtained by distributing the signs \$+1\$ and \$-1\$ to the numbers, that are “only” \$2001\$ possible target sums.

So the idea is to maintain a list L of length \$2001\$, corresponding to the possible target sums \$-1000 \ldots 1000\$. At each point in the following iteration L[i + 1000] is the number of ways to obtain the target sum i with the numbers encountered so far.

Initially, L[1000] = 0 and all other entries are zero, because 0 is the only target sum that can be obtained using none of the numbers.

Then you iterate over the given array of numbers and update the list L.

Ultimately, L[S + 1000] is the wanted number of ways to obtain the target sum S using all the given numbers.

This approach has \$ O(n) \$ time complexity, which is asymptotially much better than \$O(2^n)\$ of your original approach.

Answer 2

Python has a recursion limit. By default, this is only about 1000 stack levels deep, and depending on your input, that cap might be reached by your recursion.

If you used the same input as the assignment did, then I have a rather hard time believing you timed out. Your function would be called only 1+2^4 = 17 times.

I ran it with the assignment inputs and it finished straight away.