464. Can I Win

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.

class Solution {
private:
    bool isWin(unordered_map<int, bool>& dp, int choosed, int& maxChoosable, int left) {
        if(left <= 0)
            return false;
        
        if(dp.find(choosed) != dp.end())
            return dp[choosed];

        for(int i = 0; i < maxChoosable; i++) {
            if(!(choosed & (1<<i)) && !isWin(dp, choosed | (1<<i), maxChoosable, left - i - 1)) {
                return dp[choosed] = true;
            }
        }
        return dp[choosed] = false;
    }
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        unordered_map<int, bool> dp;
        return maxChoosableInteger >= desiredTotal ? true : maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal ? false : isWin(dp, 0, maxChoosableInteger, desiredTotal);
    }
};