Java 6~8ms Backtrack Solution, no extra space


  • 0
    T

    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 
        }
    }
    }

Log in to reply
 

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