Problem statement

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

Solution

Let n = maxChoosableInteger. Then we can define position in our game as binary mask with n bits (we have also number desiredTotal = m minus already used number, but it can be defined uniquely).

Complexity

From every position we can take no more than n turns, so we can use DP on O(2^n) positions - space complexity with O(n 2^n) time complexity (if we do not use memorization it will be O(n!)).

Code

class Solution(object):
    def canIWin(self, n, m):
        if (1 + n) * n//2 < m: return False
        
        @lru_cache(None)  
        def dp(mask, t):
            for i in range(n):
                if 1<<i & mask:
                    if i+1 >= t or not dp(mask^1<<i, t-i-1): return True
            return False
        
        return dp((1<<n)-1, m)