C++ solution with comments, 19 ms


  • 2
    K
    class Solution {
       int _maxChoosableInteger;
       int _desiredTotal;
       vector<char> dp;
    
       bool makeMove(int total, int movesMask) {
          // obviously loosing state, because the player cannot make any moves
          if (total >= _desiredTotal)
             return false;
    
          // use already calculated state if any
          if (dp[movesMask] != -1)
             return dp[movesMask];
    
          // try all possible moves that are left
          for (int i = 0; i < _maxChoosableInteger; ++i) {
             if (movesMask & (1 << i))
                continue;
             movesMask |= (1 << i);
             // if there is a move that leads from the current state to a losing state,
             // the current state is a winning state, and otherwise it is a losing state
             if (!makeMove(total + i + 1, movesMask))
             {
                movesMask &= ~(1 << i);
                dp[movesMask] = true;
                return true;
             }
             movesMask &= ~(1 << i);
          }
    
          dp[movesMask] = false;
          return false;
       }
    
    public:
       bool canIWin(int maxChoosableInteger, int desiredTotal) {
          int sum = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
          if (sum < desiredTotal) return false;
          if (desiredTotal <= 0) return true;
    
          _maxChoosableInteger = maxChoosableInteger;
          _desiredTotal = desiredTotal;
          
          dp.assign(1 << maxChoosableInteger, -1);
          return makeMove(0, 0);
       }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.