C++ | Recursion | dfs | without using mask
Inspired by Votrubac\'s solution \n1.  We make a players string with all 1s\n1. If a player looses we mark it as 0\n1. We maintain l = left and r = right bounds
**Inspired by [Votrubac\'s solution ](https://leetcode.com/problems/the-earliest-and-latest-rounds-where-players-compete/discuss/1268539/Recursion)**\n1.  We make a players string with all 1s\n1. If a player looses we mark it as 0\n1. We maintain l = left and r = right bounds \n1. New round begins when l >= r means either 1 player remains or no player remains\n\n**Approach 1 (500ms)**\n```\nclass Solution {\npublic:\n    int f, s, n;\n    int maxr = INT_MIN, minr = INT_MAX;\n    vector<int> earliestAndLatest(int N, int F, int S) {\n        f = F-1, s = S-1, n = N;\n        string players = string(n, \'1\');\n\t\tint round = 1, left = 0, right = n-1;\n        help(players, left, right, round);\n        return {minr, maxr};\n    }\n    \n    //passing players by reference is crucial to avoid tle\n    void help(string &players, int l, int r, int round){\n        \n        //round finished start next round\n        if(l >= r){\n            help(players, 0, n-1, round+1);\n        }\n        //left player is already eliminated continue with other players\n        else if(players[l] == \'0\'){\n            help(players, l+1, r, round);\n        }\n        //right player is already eliminated continue with other players\n        else if(players[r] == \'0\'){\n            help(players, l, r-1, round);\n        }\n        //we have found the place where first and second players come head to head\n        else if((l == f and r == s) or (l == s and r == f)){\n            minr = min(minr, round);\n            maxr = max(maxr, round);\n        }\n        //the left player will win this match\n        else if(l == f || l == s){\n            //make the right player loose\n            players[r] = \'0\';\n            help(players, l+1, r-1, round);\n            //reset for more exploration (more exploration happens when an earlier call was made from the last else block)\n            players[r] = \'1\';\n        }\n        //the right player will win this match\n        else if(r == f || r == s){\n            //make the left player loose\n            players[l] = \'0\';\n            help(players, l+1, r-1, round);\n            //reset for more exploration (more exploration happens when an earlier call was made from the last else block)\n            players[l] = \'1\';\n        }\n        else{\n            //both can win or loose, perform both scenarios\n            players[r] = \'0\';\n            help(players, l+1, r-1, round);\n            players[r] = \'1\';\n            players[l] = \'0\';\n            help(players, l+1, r-1, round);\n            players[l] = \'1\';\n        }\n    }\n};\n```\n\n**Approach 2 (extention of approach 1) (16ms)**\n1. We memoize the state (players) of help function using a key.\n1. key = ```NUMBER_OF_PLAYERS_BEFORE_FIRST_PLAYER + | + NUMBER_OF_PLAYERS_BETWEEN_FIRST_AND_SECOND_PLAYER + | + NUMBER_OF_PLAYERS_AFTER_SECOND_PLAYER```\n1. All these are number of players still left means they have value = 1\n1. This key is stored in visited.\n```\nclass Solution {\npublic:\n    int f, s, n;\n    int maxr = INT_MIN, minr = INT_MAX;\n    unordered_set<string> visited;\n    \n    vector<int> earliestAndLatest(int N, int F, int S) {\n        f = F-1, s = S-1, n = N;\n        string players = string(n, \'1\');\n\t\tint round = 1, left = 0, right = n-1;\n        help(players, left, right, round);\n        return {minr, maxr};\n    }\n    \n    //passing players by reference is crucial to avoid tle\n    void help(string &players, int l, int r, int round){\n        \n        //round finished start next round\n        if(l >= r){\n            help(players, 0, n-1, round+1);\n        }\n        //left player is already eliminated continue with other players\n        else if(players[l] == \'0\'){\n            help(players, l+1, r, round);\n        }\n        //right player is already eliminated continue with other players\n        else if(players[r] == \'0\'){\n            help(players, l, r-1, round);\n        }\n        //we have found the place where first and second players come head to head\n        else if((l == f and r == s) or (l == s and r == f)){\n            minr = min(minr, round);\n            maxr = max(maxr, round);\n        }\n        //the left player will win this match\n        else if(l == f || l == s){\n            //make the right player loose\n            players[r] = \'0\';\n            help(players, l+1, r-1, round);\n            //reset for more exploration (more exploration happens when an earlier call was made from the last else block)\n            players[r] = \'1\';\n        }\n        //the right player will win this match\n        else if(r == f || r == s){\n            //make the left player loose\n            players[l] = \'0\';\n            help(players, l+1, r-1, round);\n            //reset for more exploration (more exploration happens when an earlier call was made from the last else block)\n            players[l] = \'1\';\n        }\n        else if(visited.count(getPlayersBeforeBetweenAndAfterFAndS(players)) == 0){\n            visited.insert(getPlayersBeforeBetweenAndAfterFAndS(players));\n            \n            //both can win or loose, perform both scenarios\n            players[r] = \'0\';\n            help(players, l+1, r-1, round);\n            players[r] = \'1\';\n            players[l] = \'0\';\n            help(players, l+1, r-1, round);\n            players[l] = \'1\';\n        }\n    }\n    \n    string getPlayersBeforeBetweenAndAfterFAndS(string &s1){\n        int d1 = 0, d2 = 0, d3 = 0;\n        for(int i = 0; i < s1.size(); i++){\n            if(i < min(f, s) and s1[i] == \'1\'){\n                d1++;\n            }\n            else if(min(f,s) < i and i < max(f,s) and s1[i] == \'1\'){\n                d2++;\n            }\n            else if(i > max(f,s) and s1[i] == \'1\'){\n                d3++;\n            }\n        }\n        return to_string(d1) + "|" + to_string(d2) + "|" + to_string(d3) ;\n    }\n};\n```\n
['C']