[LeetCode] 464. Can I Win

 Problem : https://leetcode.com/problems/can-i-win/

The state of this game is the integers be used. Because maximal number of integer is no more than 20.  

We can use bitmask to remember the used integers. 

Also use True to represent the first player wins and use False to represent the second player wins.

Time complexity = O( 2 ** N ).   For each integer we consider whether use it or not to form a new state.  There are 2 ** N states. 

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        
        # use bitmask to remember the picked integer
        mask = 0
        
        @cache
        def helper(mask, sums, a):
            for i in range(maxChoosableInteger):
                
                # bypass if the integer (i+1) is already used
                if mask & (1 << i) != 0:
                    continue
                
                # current player wins when sums >= desiredTotal
                if sums + i + 1 >= desiredTotal:
                    return a
                
                # mark integer (i+1) is used
                mask ^= (1 << i)
                
                # because both players play optimally
                # we consider current player must chooses this routine
                # which leads to a win result for hime
                if helper(mask, sums + i + 1, not a) ==  a:
                    
                    # mark integer (i+1) is not used
                    mask ^= (1 << i)
                    
                    # current player can force a win
                    return a
                
                # mark integer (i+1) is not used
                mask ^= (1 << i)
            
            # current player cannot force a win
            return not a
        
        # it is impossible to win whe sum of all integers is less than the desiredTotal
        if maxChoosableInteger * (maxChoosableInteger + 1) // 2 < desiredTotal: return False
        
        return helper(0, 0, True)