Help! TLE on last test case without adding additional condition.

  • 0

    When I dont add additional condition for the following case:
    "when sum of all numbers is equal to the desired sum"
    I am getting TLE on the last test case (18,171).
    Could someone let me know what I'm doing wrong?

    class Solution(object):
        def canPlayerwin(self, nums, desiredTotal):
            hash = str(nums + [desiredTotal])
            if nums[-1] >= desiredTotal:
                self.memo[hash] = True
                return True
            if hash in self.memo:
                return self.memo[hash]
            for i in range(len(nums)):
                if not self.canPlayerwin(nums[:i]+nums[i+1:], desiredTotal-nums[i]):
                    self.memo[hash] = True
                    return True
            self.memo[hash] = False
            return False
        def canIWin(self, maxChoosableInteger, desiredTotal):
            sum = maxChoosableInteger*(maxChoosableInteger+1)/2
            if sum < desiredTotal:
                return False
            elif sum == desiredTotal:
                return maxChoosableInteger%2 != 0
            self.memo = {}
            nums = list(range(1,maxChoosableInteger+1))
            return self.canPlayerwin(nums, desiredTotal)

Log in to reply

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