c++ | dfs with explanation
Idea\nThe obvious strategy of every player is :\n1. If any move is left which will form a number not divisible by 3, then the player will choose that move and c
<b>Idea</b>\nThe obvious strategy of every player is :\n1. If any move is left which will form a number not divisible by 3, then the player will choose that move and continue the game.\n2. If no such move is left, the player looses the game\n3. At last, if no move is left, then Bob is the obvious winner ( as per the question ).\n\nNote that since Alice starts first, she has the freedom to decide which out of 1 or 2 ( if available ) she has to pick in order to win. Rest is simple dfs.\nTime : O(n)\n```\nclass Solution {\npublic:\nbool help(vector<int> &v,int sum,bool aliceTurn){\n    if(sum==1 && v[1]){\n        v[1]--;\n        bool tmp=help(v,(sum+1)%3,!aliceTurn);\n        v[1]++;\n        return tmp;\n    }else if(sum==1 && v[0]){\n        v[0]--;\n        bool tmp=help(v,sum,!aliceTurn);\n        v[0]++;\n        return tmp;\n    }else if(sum==2 && v[2]){\n        v[2]--;\n        bool tmp=help(v,(sum+2)%3,!aliceTurn);\n        v[2]++;\n        return tmp;\n    }else if(sum==2 && v[0]){\n        v[0]--;\n        bool tmp=help(v,sum,!aliceTurn);\n        v[0]++;\n        return tmp;        \n    }else if(max({v[0],v[1],v[2]})){\n        // a divisible of 3 is formed by the current player\n        if(aliceTurn) return false;\n        return true;\n    }else{\n        // nothing left\n        return false;   //  bob wins\n    }\n}\n\nbool stoneGameIX(vector<int>& ar) {\n    vector<int> v(3, 0);\n    for (auto it : ar) v[it % 3]++;\n    bool aliceWins=false;\n    if(v[1]){\n        v[1]--;\n        aliceWins=(aliceWins||help(v,1,false));\n        v[1]++;\n    }\n    if(v[2]){\n        v[2]--;\n        aliceWins=(aliceWins||help(v,2,false));\n        v[2]++;\n    }\n    return aliceWins;\n}\n};\n```\n\n<b>Note</b> that this code is also accepted. The only change is changing the position of `if(sum==1 && v[1])` and `if(sum==1 && v[0])`  in the <b>help</b> function . ( which implies there\'s no compulsion to choose 1 instead of 2 or vice versa if both options are available ). \n```\nclass Solution {\npublic:\nbool help(vector<int> &v,int sum,bool aliceTurn){\n    if(sum==2 && v[2]){\n        v[2]--;\n        bool tmp=help(v,(sum+2)%3,!aliceTurn);\n        v[2]++;\n        return tmp;\n    }else if(sum==2 && v[0]){\n        v[0]--;\n        bool tmp=help(v,sum,!aliceTurn);\n        v[0]++;\n        return tmp;        \n    }else if(sum==1 && v[1]){\n        v[1]--;\n        bool tmp=help(v,(sum+1)%3,!aliceTurn);\n        v[1]++;\n        return tmp;\n    }else if(sum==1 && v[0]){\n        v[0]--;\n        bool tmp=help(v,sum,!aliceTurn);\n        v[0]++;\n        return tmp;\n    }else if(max({v[0],v[1],v[2]})){\n        // a divisible of 3 is formed by the current player\n        if(aliceTurn) return false;\n        return true;\n    }else{\n        // nothing left\n        return false;   //  bob wins\n    }\n}\n\nbool stoneGameIX(vector<int>& ar) {\n    vector<int> v(3, 0);\n    for (auto it : ar) v[it % 3]++;\n    bool aliceWins=false;\n    if(v[1]){\n        v[1]--;\n        aliceWins=(aliceWins||help(v,1,false));\n        v[1]++;\n    }\n    if(v[2]){\n        v[2]--;\n        aliceWins=(aliceWins||help(v,2,false));\n        v[2]++;\n    }\n    return aliceWins;\n}\n};\n```
[]