Problem 494, Python solution exceeded time limit, despite running successfully on the same test case
EmperoR
65

Submission of my code exceeded time limit on test case:
[2,20,24,38,44,21,45,48,30,48,14,9,21,10,46,46,12,48,12,38]
48
However, when I ran the same case, it finished normally, really weird.
Does anyone know the reason?

class Solution(object):
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        if not nums and S != 0:
            return 0
        return self.targetSum(nums, S, 0)
        
    def targetSum(self, nums, S, res):
        """
        :type nums: List[int]
        :type S: int
        :type res: int
        :rtype: int
        """
        if len(nums) == 1 and nums[0] == S:
            res += 1
        if len(nums) == 1 and nums[0] * -1 == S:
            res += 1
        if len(nums) > 1:
            res += self.targetSum(nums[1:], S - nums[0], res) + self.targetSum(nums[1:], S + nums[0], res)
        return res
Comments (2)