7-liner C++ beat 98.4%, DFS with early termination check (detailed explanation)


  • 8

    For short notation, let M = maxChoosableInteger and T = desiredTotal.

    Key Observation: the state of the game is completely determined by currently available numbers to pick in the common pool.

    State of Game: initially, we have all M numbers [1, M] available in the pool. Each number may or may not be picked at a state of the game later on, so we have maximum 2^M different states. Note that M <= 20, so int range is enough to cover it. For memorization, we define int k as the key for a game state, where

    • the i-th bit of k, i.e., k&(1<<i) represents the availability of number i+1 (1: picked; 0: not picked).

    At state k, the current player could pick any unpicked number from the pool, so state k can only go to one of the valid next states k':

    • if i-th bit of k is 0, set it to be 1, i.e., next state k' = k|(1<<i).

    Recursion: apparently

    • the current player can win at state k iff opponent can't win at some valid next state k'.

    Memorization: to speed up the recursion, we can use a vector<int> m of size 2^M to memorize calculated results m[k] for state key k:

    • 0 : not calculated yet;
    • 1 : current player can win;
    • -1: current player can't win.

    Initial State Check:
    There are several checks to be done at initial state k = 0 for early termination so we won't waste our time for DFS process:

    1. if T < 2, obviously, the first player wins by simply picking 1.
    2. if the sum of entire pool S = M*(M+1)/2 is less than T, of course, nobody can reach T.
    3. if the sum S == T, the order to pick numbers from the pool is irrelevant. Whoever picks the last will reach T. So the first player can win iff M is odd.
        bool canIWin(int M, int T) {
          int S = M*(M+1)/2; // sum of entire pool
          return T<2? true : S<T? false : S==T? M%2 : dfs(M,T,0);
        }
        
        bool dfs(int M, int T, int k) {
          if (T<=0 || m[k]) return T>0 && m[k]>0; // memorization or total reached by opponent
          for (int i = 0; i < M; ++i)
            if (!(k&1<<i) && !dfs(M, T-i-1, k|1<<i)) return m[k] = 1; // current player wins
          return !(m[k] = -1); // current player can't win
        }
        
        int m[1<<20] = {}; // m[key]: memorized result when pool state = key
    

Log in to reply
 

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