4
\$\begingroup\$

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/

\$\endgroup\$
  • \$\begingroup\$ “Please refrain from commenting that the method can exist as a function on its own” – The policy on this site is that an answer can review any aspect of the posted code. Related on meta: codereview.meta.stackexchange.com/q/9345/35991. \$\endgroup\$ – Martin R Oct 12 at 15:49
  • \$\begingroup\$ Consider it leetcode's mistake for encouraging bad coding practices. \$\endgroup\$ – Gloweye Oct 12 at 16:24
  • 1
    \$\begingroup\$ When I run that code with the input from the assignment,it doesn't time out. What inputs did you use that broke it ? \$\endgroup\$ – Gloweye Oct 12 at 16:50
  • \$\begingroup\$ you need to keep the information of already calculated steps for saving time aka memoization \$\endgroup\$ – temmo Oct 14 at 2:19
3
\$\begingroup\$

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

  1. 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.

\$\endgroup\$
  • \$\begingroup\$ And I don't want to deprive you from the satisfaction to implement that successfully, therefore I don't post any code :) \$\endgroup\$ – Martin R Oct 12 at 17:04
  • \$\begingroup\$ Space complexity : O(n). The depth of recursion tree can go upto n - It should be O(l*n) \$\endgroup\$ – temmo Oct 14 at 2:18
  • 1
    \$\begingroup\$ @prashantrana: Yes, but what I meant is the time complexity, and that is O(2^n) for the original algorithm. \$\endgroup\$ – Martin R Oct 14 at 4:44
1
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ This should essentially exist as a comment, not an answer - it's a prompt for more detail \$\endgroup\$ – Reinderien Oct 12 at 16:47
  • \$\begingroup\$ Edited it. Now it describes the most probably cause for timing out like he did, and removed the info prompt part. \$\endgroup\$ – Gloweye Oct 12 at 16:51
  • \$\begingroup\$ @Gloweye did it pass all test cases? If so, please post the code \$\endgroup\$ – nz_21 Oct 12 at 17:17
  • \$\begingroup\$ @Gloweye: The array can have up to 20 elements, that makes 2^20 = 1048576 function calls, and that might be a reason for the timeout. \$\endgroup\$ – Martin R Oct 12 at 17:24
  • \$\begingroup\$ I must have missed that bit in the explanation on that other side, then. @nz_21, please do edit those testcases into your question. \$\endgroup\$ – Gloweye Oct 12 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.