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.

Example 1:

Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false
Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.

Example 2:

Input: maxChoosableInteger = 10, desiredTotal = 0
Output: true

Example 3:

Input: maxChoosableInteger = 10, desiredTotal = 1
Output: true

Constraints:

• 1 <= maxChoosableInteger <= 20

• 0 <= desiredTotal <= 300

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        # n*(n+1)//2
        total_sum = (maxChoosableInteger+1) * maxChoosableInteger // 2
        if total_sum < desiredTotal:
            return False
        if total_sum == desiredTotal:
            return maxChoosableInteger % 2
        self.seen = {}
        choices = list(range(1, maxChoosableInteger+1))
        return self.recursion(choices, desiredTotal)
        
    def recursion(self, choices, remainder):
        # Since Choices is sorted and if last element of choice exceeds remainder 
        # then their is win
        if choices[-1] >= remainder:
            return True
        key = tuple(choices)
        if key in self.seen:
            return self.seen[key]
        for index in range(len(choices)):
            if not self.recursion(choices[:index] + choices[index+1:], remainder - choices[index]):
                self.seen[key] = True
                return True
        self.seen[key] = False
        return False