464.-can-i-win.md

464. Can I Win

• Medium

• In the "100 game" two players take turns adding, to a running total, any integer from 1 to 10. The player who first causes the running total to reach or exceed 100 wins.

  What if we change the game so that players cannot re-use integers?

  For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total >= 100.

  Given two integers maxChoosableInteger and desiredTotal, return true if the first player to move can force a win, otherwise, return false. Assume both players play optimally.

Analysis

There are two easy-to-identify cases in this problem. Namely when the sum of all the possible choices is less than the desired sum. Or when the sum is equal to the desired sum. For the rest of the cases, we use a dictionary and a tuple to record what we have seen and try to go through all the cases to see if there is such a "win".

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        seen={}
        def can_win(choices,remainder):
            if choices[-1]>=remainder:
                return True
            
            seen_key=tuple(choices)
            if seen_key in seen:
                return seen[seen_key]
            
            for index in range(len(choices)):
                if not can_win(choices[:index]+choices[index+1:],remainder-choices[index]):
                    seen[seen_key]=True
                    return True
                
            seen[seen_key]=False
            return False
        
        summed_choices=(maxChoosableInteger+1)*maxChoosableInteger/2
        if summed_choices<desiredTotal:
            return False 
        
        if summed_choices==desiredTotal:
            return maxChoosableInteger%2
        
        choices=list(range(1,maxChoosableInteger+1))
        return can_win(choices, desiredTotal)