class Solution {
public:

   map<pair<int ,int> , int>dp;


    int  chanceOfWinning(int maxInteger , int total , int mask){

        if(total <=0) return 0 ;

        if(dp.find({mask ,total}) != dp.end())return dp[{mask , total}] ;

        int  chanceOtherPlayer = 0;

        for(int i=0; i<maxInteger ; i++){
            int b1 = mask & (1<<i);
            if(b1 == 0){


        chanceOtherPlayer |= chanceOfWinning(maxInteger , total - i-1 , mask|1<<i);
            }
        }

        return  dp[{mask , total}] = (chanceOtherPlayer ^ 1) ;
    }



    bool canIWin(int maxChoosableInteger, int desiredTotal) {

        int maxSum = (maxChoosableInteger * (maxChoosableInteger+1))/2;


        if(maxSum < desiredTotal)return false;

        if(desiredTotal <= 0)return true ;

         dp.clear();

        return  chanceOfWinning(maxChoosableInteger ,   desiredTotal,  0 );



    }
};