Python, 12 lines


  • 0
    B
    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:
                        continue
                    if num >= total or not self.helper(max, total-num, used | 1 << num, cached):
                        cached[used] = True
                        break
            return cached[used]
    

Log in to reply
 

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