# 1-liner C++ DFS solution, no helper function (detailed explanation)

• Key Observation:

• Only the score difference `int sd` and tiebreaker `bool tb` matter in the game's outcome, i.e., a player wins if and only if his `sd + tb > 0`.

• Player 1 can be guaranteed to win with scores `a[0:N-1]` if and only if Player 2 can be guaranteed to lose with remaining scores `a[1:N-1]` or `a[0:N-2]` to overcome the deficit score of `a[0]` or `a[N-1]`.

Then it is easy to define a DFS routine to check if the current player can win with remaining score index range `[s,e)`, current score difference `sd` and tiebreaker `tb` (true/false) by adding some default variables.

1-liner, practically :-)

``````    bool PredictTheWinner(vector<int>& a, int s = 0, size_t e = INT_MAX, int sd = 0, bool tb = true) {
return s==e? sd+tb>0 : !PredictTheWinner(a, s+1, e=min(e,a.size()), -sd-a[s],   !tb) ||
!PredictTheWinner(a, s,   e-1,               -sd-a[e-1], !tb);
}
``````

Since the array length `a.size() <= 20`, I didn't bother to memorize previous DFS results.

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