Leetcode Can I Win problem solution

In this Leetcode Can I Win problem solution 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.

Problem solution in Python.

def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        m, d = maxChoosableInteger, desiredTotal
        @lru_cache(None)
        def pick(num, left):
            for i, n in enumerate(num):
                # either i win now or another player lose in next turn
                if n>=left or not pick(num[:i] + num[i+1:], left-n):
                    return True
            return False
        if m >= d:
            return True
        if m*(m+1)/2 < d:
            return False
        return pick(tuple([i for i in range(1, m+1)]), d)

Problem solution in Java.

class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal <= 0) return true;
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
        int[] dp = new int[1 << maxChoosableInteger];
        return dfs(dp, 0, maxChoosableInteger, desiredTotal);
    }
    
    public boolean dfs(int[] dp, int chs, int max, int target) {
        // targer <= 0 means the prior one wins
        if (target <= 0) return false;
        if (dp[chs] != 0) return dp[chs] == 1;
        boolean win = false;
        for (int i = 0; i < max; i++) {
            // i + 1 not use
            if ((chs & (1 << i)) == 0) {
               win = win || !dfs(dp, chs ^ (1 << i), max, target - i - 1);
            }
        }
        dp[chs] = win ? 1 : -1;
        return win;
    }
}

Problem solution in C++.

class Solution {
public:
　　bool canIWin(int maxChoosableInteger, int desiredTotal) {
　　　　if (maxChoosableInteger >= desiredTotal) return true;
　　　　int sum = ((maxChoosableInteger + 1) * maxChoosableInteger) >> 1;
　　　　if (sum < desiredTotal) return false;
　　　　mp = vector<int>(1 << maxChoosableInteger, -1);
　　　　return canWin(0, maxChoosableInteger, desiredTotal);
　　}
private:
　　vector<int> mp;
　　bool canWin(int used, const int &maxChoosableInteger, int desiredTotal) {
　　　　if (mp[used] != -1) return mp[used];
　　　　for (int i = maxChoosableInteger, bits = 1 << (maxChoosableInteger - 1); i >= 1; --i, bits >>= 1) {
　　　　　　if ((used & bits) != 0) continue;
　　　　　　if (i >= desiredTotal || !canWin(used | bits, maxChoosableInteger, desiredTotal - i)) {
　　　　　　　　mp[used] = 1;
　　　　　　　　return true;
　　　　　　}
　　　　}
　　　　mp[used] = 0;
　　　　return false;
　　}
};