C++ top-down solution


  • 0
    class Solution {
    public:
        bool PredictTheWinner(vector<int>& nums) {
            return win(nums, 0, nums.size()-1, 0, true);
        }
        
        bool win(vector<int>& nums, int left, int right, int sum, bool p1) {
            if (left > right) {
                if (p1) return sum >= 0;
                else return sum < 0;
            }
            bool res = false;
            if (p1) res = !win(nums, left+1, right, sum+nums[left], !p1) || !win(nums, left, right-1, sum+nums[right], !p1);
            else res = !win(nums, left+1, right, sum-nums[left], !p1) || !win(nums, left, right-1, sum-nums[right], !p1);
            return res;
        }
    };
    

Log in to reply
 

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