classSolution{public:boolcanIWin(intmaxChoosableInteger,intdesiredTotal){if(desiredTotal<=0)returntrue;constintsum=maxChoosableInteger*(maxChoosableInteger+1)/2;if(sum<desiredTotal)returnfalse;returndp(desiredTotal,0,maxChoosableInteger);}private:unordered_map<int,bool>memo;// True: can win, false: can't win// State: record integers that have been chosenbooldp(inttotal,intstate,intn){if(total<=0)returnfalse;if(memo.count(state))returnmemo[state];for(inti=1;i<=n;++i){if(state&1<<i)// Integer i is usedcontinue;if(!dp(total-i,state|1<<i,n))returntrue;}returnmemo[state]=false;}};
classSolution{publicbooleancanIWin(intmaxChoosableInteger,intdesiredTotal){if(desiredTotal<=0)returntrue;finalintsum=maxChoosableInteger*(maxChoosableInteger+1)/2;if(sum<desiredTotal)returnfalse;returndp(desiredTotal,0,maxChoosableInteger);}// True: can win, false: can't winprivateMap<Integer,Boolean>memo=newHashMap<>();// State: record integers that have been chosenprivatebooleandp(inttotal,intstate,intn){if(total<=0)returnfalse;if(memo.containsKey(state))returnmemo.get(state);for(inti=1;i<=n;++i){if((state&1<<i)==1)// Integer i is usedcontinue;if(!dp(total-i,state|1<<i,n))returntrue;}memo.put(state,false);returnfalse;}}