#include <numeric>
class Solution {
public:
    bool win(bool& mewin,bool me,vector<bool>& n,int dt)
    {
        for(int i=1;i<n.size();i++)
        {
            if(n[i]) continue;
            if(i>=dt)
            {
                return true;
            }
            n[i]=true;
            bool w = win(mewin,!me,n,dt-i);
            if(!w && me) mewin = true;
            n[i]=false; 
        }
        return false;
    }
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if(maxChoosableInteger>=desiredTotal) return true;
        int sum = 0;
        vector<bool> n(maxChoosableInteger+1);
        for(int i=1;i<n.size();i++)
        {
            n[i] = false;
            sum+=i;
        }
        if(sum<desiredTotal) return false;
        bool mewin = false;
        win(mewin, true, n, desiredTotal);
        return mewin;
    }
};