C++ Recursive Solution

  • 0

    My idea is to check if the Player 1 can get half of the total scores at least.

    bool canWin(int goal, vector<int>& nums, int i, int j)
            if(goal <= 0) return true;
            if(i <= j) //Player 1 picks i  ||  Player 1 picks j
                return canWin(goal-nums[i], nums, i+2, j) && canWin(goal-nums[i], nums, i+1, j-1)
                    || canWin(goal-nums[j], nums, i+1, j-1) && canWin(goal-nums[j], nums, i, j-2);
            return false;
        bool PredictTheWinner(vector<int>& nums) {
            int goal = accumulate(nums.begin(), nums.end(), 0);
            goal = (goal+1) / 2;
            return canWin(goal, nums, 0, nums.size()-1);

Log in to reply

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