<p>You are given an integer array <code>nums</code>. Two players are playing a game with this array: player 1 and player 2.</p>

<p>Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of <code>0</code>. At each turn, the player takes one of the numbers from either end of the array (i.e., <code>nums[0]</code> or <code>nums[nums.length - 1]</code>) which reduces the size of the array by <code>1</code>. The player adds the chosen number to their score. The game ends when there are no more elements in the array.</p>

<p>Return <code>true</code> if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return <code>true</code>. You may assume that both players are playing optimally.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,5,2]
<strong>Output:</strong> false
<strong>Explanation:</strong> Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return false.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,5,233,7]
<strong>Output:</strong> true
<strong>Explanation:</strong> Player 1 first chooses 1. Then player 2 has to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 20</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>7</sup></code></li>
</ul>

class Solution{
public:
    // Create a Recursive 'Solve()' function which will return true if the score of 'player1' is greater than or equal to the
    // score of 'player2' 
    bool Solve(vector<int> &nums, int i, int j, int score1, int score2, bool flag){
        // BASE CASE: If we finish selecting all the elements of the I/p Array nums, then return true of 'player1' has
        // more or equal score than 'player2' 
        if(i > j) return score1 >= score2;

        // If 'player1' has the current turn, then he has 2 choices: 
        // Choice 1: Add the 'i'th element to his score and ask Recursion to do the rest of the job by passing 'flag = false'
        // because in next turn, 'player2' will have the turn
        // Choice 2: Add 'j'th element to his score and ask recursion to do remaining task 
        if(flag){
            bool choice1 = Solve(nums, i + 1, j, score1 + nums[i], score2, false); // since we selected 'i'th, go for 'i+1'th
            bool choice2 = Solve(nums, i, j - 1, score1 + nums[j], score2, false); // since we selected 'j'th, next is 'j-1'th
         
            // If 'player1' can win in any 1 of the above case, return true.
            return (choice1 || choice2); 
        }
        else{
            // Similarly, 'player2' will also have 2 choices as 'player1
            bool choice1 = Solve(nums, i + 1, j, score1, score2 + nums[i], true); // Add 'i'th element 
            bool choice2 = Solve(nums, i, j - 1, score1, score2 + nums[j], true); // Add 'j'th element 
    
            // If 'player2' wins in both the 2 cases, he will be the final winner
            return (choice1 && choice2);
        }
        return 0;
    }

    bool predictTheWinner(vector<int>& nums){
        // Approach: RECURSION 
        // Self Solved 
        // TC : O(2 ^ n) 
        // SC : O(2 ^ n)
        // C++ CODE: 
        int score1 = 0; // to stroe the maximum score 'player1' can get 
        int score2 = 0; // to store the maximum score 'player2' can get 
        int i = 0; // start of the I/p Array 
        int j = nums.size() - 1; // end of the I/p Array 
        bool flag = true; // Initially, 'player1' has the turn to select either the 'i'th or 'j'th element 

        bool canPlayer1Win = Solve(nums, i, j, score1, score2, flag); // Ask Recursion if 'player1' can win or not

        return (canPlayer1Win ? true : false);
    }
};
8900