# 464. Can I Win

Two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example:

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.

# Solution

Approach 1: (memoized) recursion.

# Code (Python)

Approach 1:

    def canIWin(self, upper_bound: int, total: int) -> bool:
        if total == 0:
            return True
        if (1 + upper_bound) * upper_bound / 2 < total:
            return False
        if (1 + upper_bound) * upper_bound / 2 == total:
            return True if upper_bound % 2 == 1 else 0
        #return self._play([i for i in range(1, upper_bound + 1)], total)
        return self._play_with_cache(tuple([i for i in range(1, upper_bound + 1)]), total, {})
    
    def _play(self, nums, left):
        if nums[-1] >= left:
            return True
        #OR:
        #if left <= 0:
        #    return False
        for i in range(len(nums)):
            if not self._play(nums[:i] + nums[i+1:], left - nums[i]):
                return True
        return False
    
    def _play_with_cache(self, nums, left, cache):
        if nums[-1] >= left:
            return True
        # the key in the cache is a tuple of nums -- no need to record sum left because it depends on what's left in nums
        if nums in cache:
            return cache[nums]
        for i in range(len(nums)):
            if not self._play(tuple(nums[:i] + nums[i+1:]), left - nums[i]):
                cache[nums] = True
                return True
        cache[nums] = False
        return False

Approach 2:

# Code (C++)

Approach 1:

Approach 2: