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

• 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
``````

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