# Java 6~8ms Backtrack Solution, no extra space

• I always like using backtrack programing instead of DP to intuitively solve a quesiton when it is about making choices. So clearly this question can be solved by backtrack going through every possible choices that 2 players can have. Let me elaborate my idea!

Let's denote the 1th player by A and denote the 2th player by B.

As the question shows, given nums[], we are trying to see whether A always have a optimal strategy to win or B always have a optimal strategy to win/prevent A's win, so let's just stand by A. Say after several runs A is the winner, then we must have SA - SB>=0, where SA is the sum of all A get and SB is the sum of all B get.

So now let's get started from the beginning, initially before A and B making choices, Total = SA - SB=0.

(1) Then A have two choices:
(A.1) Pick nums[left] and set Total = Total + nums[left++], then go to (2) to see if this choice is optimal to guarantee A's win, if it is, we return true to indicate A as winner, else we go for A.2.
(A.2) Pick nums[right] and set Total = Total + nums[right--], then go to (2) to see if this choice is optimal to guarantee A's win, if it is, we return true to indicate A as winner, else we return false to indicate B as winner/A as loser.

(2) Once A have made either choice above, B have two choices:
(B.1) Pick nums[left] and set Total = Total - noms[left++], then go to (1) to see if this choice is optimal to guarantee B's win, if it is, we return false to indicate B as winner, else we go for B.2.
(B.2) Pick nums[right] and set Total = Total - nums[right--], then go to (1) to see if this choice is optimal to guarantee B's win, if it is, we return false to indicate B as winner, else we return true to indicate A as winner/B as loser.

Once left==right, we know that A and B have no choices, then A win if Total>=0, else B win

``````public class Solution {
public boolean PredictTheWinner(int[] nums) {
return predictHelper(nums,0, 0,nums.length-1);
}
public boolean predictHelper(int[] nums, int total, int left, int right){
if(left==right){//A and B have no choices
if(total>=0) return true;  //A's win
else return false; //B's win
}
else if(left<right){ //player A making choices
if(predictHelper(nums, total+nums[left++], right, left)||   //try A.1
predictHelper(nums, total+nums[right--], right, --left))    //backtrack to reset left pointer and try A.2
return true; //A.1 or A.2 can guarantee A's win
else return false; //A will always lose given the current strategy
}
else {//player B making choices
if(!predictHelper(nums, total-nums[right++], right, left)||   //try B.1
!predictHelper(nums, total-nums[left--], --right, left))    //backtrack to reset right pointer and try B.2
return false; //B.1 or B.2 can guarantee B's win
else return true; //B will always lose given the current strategy
}
}
}``````

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