class Solution {
unordered_map<unsigned int,bool> cache;
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
if(maxChoosableInteger>=desiredTotal) return true;
//the sum of all available numbers are less than desireTotal, which means it cannot reach the desireTotal
if((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;
unsigned int used = (1<<maxChoosableInteger)1; // use bit to record which number has been used (bit '1' means available, bit '0' means used)
return play(desiredTotal,used,maxChoosableInteger);
}
bool play(int target, unsigned int used, int size){
if(cache.find(used) != cache.end()) return cache[used];
//exist available integer >= target, return true
if(target1<size && (used > (1<<target1))){
cache[used] = true;
return true;
}
int bit = 1;
for(int i = 0; i<size; i++,bit <<=1){
if((used & bit)== 0) continue; // the (i+1)th bit is '0', means (i+1) is used
used ^= bit;
if(!play(targeti1,used,size)){
used = bit;
cache[used] = true;
return true;
}
used = bit;
}
cache[used] = false;
return false;
}
};
C++ easy understood 269ms solution with comments


@songruibin Actually desiredTotal is a function of bits. So it's not needed in the cache.

a little change to make it more clear.
And @songruibin At first, I have the same question as you, so I use dp[2^20][300], then I realize
for a certain desiredTotal, eachused
correspond to a desired num(desiredTotal  the number has been used) so we don't need to store the desiredTotal in cache.
However, if we want to get the result for more than once, store the desiredTotal incache
will reduce repeated calculation.unordered_map<int, bool> cache; bool winThis(int canUse, int d) { if (d <= 0) return false; if (cache.find(canUse) != cache.end()) return cache[canUse]; int bit = 1; int cnt = 1; while (bit<=canUse) { if (bit&canUse&&!winThis(canUse^bit,dcnt)) { cache[canUse] = true; return true; } cnt++; bit <<= 1; } return cache[canUse] = false; } bool canIWin(int maxChoosableInteger, int desiredTotal) { if (desiredTotal > (1 + maxChoosableInteger)*maxChoosableInteger / 2) return false; if (maxChoosableInteger>=desiredTotal) return true; return winThis((1<<maxChoosableInteger)1, desiredTotal); }