Python, 12 lines

  • 0
    class Solution(object):
        def canIWin(self, maxChoosableInteger, desiredTotal):
            :type maxChoosableInteger: int
            :type desiredTotal: int
            :rtype: bool
            if maxChoosableInteger**2+maxChoosableInteger < desiredTotal*2:
                return False        
            return self.helper(maxChoosableInteger, desiredTotal, 0, {})
        def helper(self, max, total, used, cached):
            if used not in cached:
                cached[used] = False
                for num in range(1, max+1):
                    if used & 1 << num:
                    if num >= total or not self.helper(max, total-num, used | 1 << num, cached):
                        cached[used] = True
            return cached[used]

Log in to reply

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