Can I Win

Intuition

Solution

class Solution:
    def canIWin(self, n: int, total: int) -> bool:
        if (1 + n) * n // 2 < total:
            return False

        nums = 2 ** n - 1
        self.cache = [None] * (nums + 1)
        return self._helper(nums, total)

    def _helper(self, nums, desired):
        if self.cache[nums] is not None:
            return self.cache[nums]

        i = 1
        current = 1
        while i <= nums:
            if not i & nums:
                pass
            elif current >= desired:
                self.cache[nums] = True
                return True
            elif not self._helper(nums ^ i, desired - current):
                self.cache[nums] = True
                return True
            i = i << 1
            current += 1
        self.cache[nums] = False
        return False