C++ Solution | Recursion + Memoization
Wrong Greedy Approach:\n\n- Sort the tasks array and keep adding the task to the current session until the sum becomes equal to or more than the sessionTime.\n-
Wrong Greedy Approach:\n\n- Sort the `tasks` array and keep adding the task to the current session until the sum becomes equal to or more than the `sessionTime`.\n- This approach fails on test cases like `tasks` = {3, 4, 7, 8, 10} `sessionTime` = 12\n\n**Solution:**\n\nWe have created a vector named `sessions`. The length of which denotes the number of work sessions we currently have, and the value at `ith` index `sessions[i]` denotes the number of work hours we have completed in the `ith` session. Now in such scenerio\n\n- Each task in the `tasks` array has two options:\n  1. Get included in one of the session in `sessions`\n  2. Get included in a new session by adding one to the `sessions`.\n\nThe minimum of the two above choices will be the answer. The below code shows the Rercursive solution.\n\n**Recursion (TLE):**\n\n```\nclass Solution {\npublic:\n    vector<int> sessions;\n\n    int solve(vector<int>& tasks, int n, int sessionTime, int pos) {\n        if (pos >= n )\n            return 0;\n\n        // adding the current task to a new session\n        sessions.push_back(tasks[pos]);\n        int ans = 1 + solve(tasks, n, sessionTime, pos + 1);\n        sessions.pop_back();\n        \n        // trying to add it to the previous active session\n        for (int i = 0; i < sessions.size();i++) {\n            if (sessions[i] + tasks[pos] <= sessionTime) {\n                sessions[i] += tasks[pos];\n                ans = min(ans, solve(tasks, n, sessionTime, pos + 1));\n                sessions[i] -= tasks[pos];\n            }\n        }\n        \n        return ans;\n    }\n    \n    int minSessions(vector<int>& tasks, int sessionTime) {\n        int n = tasks.size();\n        return solve(tasks, n, sessionTime, 0);\n    }\n};\n```\n\n\nIn order to memoize the solution, we use a unordered map from String to int `dp`. The two states which we need to memoize are the `pos` and the `sessions`. We encode both these state by concating them as string with `$` as a delimeter.\n\nNote: We first sort the `sessions` to reduce the number of repeated states.\n\n**Recursion + Memoization Code (Accepted):**\n\n```\nclass Solution {\npublic:\n    vector<int> sessions;\n    unordered_map<string , int> dp;\n    \n    string encodeState(int pos, vector<int>& sessions) {\n        vector<int> copy = sessions;\n        sort(copy.begin(), copy.end());\n        \n        string key = to_string(pos) + "$";\n        for (int i = 0; i < copy.size(); i++)\n            key += to_string(copy[i]) + "$";\n        \n        return key;\n    }\n    \n    int solve(vector<int>& tasks, int n, int sessionTime, int pos) {\n        if (pos >= n )\n            return 0;\n        \n        string key = encodeState(pos, sessions);\n        \n        if (dp.find(key) != dp.end())\n            return dp[key];\n        \n        sessions.push_back(tasks[pos]);\n        int ans = 1 + solve(tasks, n, sessionTime, pos + 1);\n        sessions.pop_back();\n        \n        for (int i = 0; i < sessions.size();i++) {\n            if (sessions[i] + tasks[pos] <= sessionTime) {\n                sessions[i] += tasks[pos];\n                ans = min(ans, solve(tasks, n, sessionTime, pos + 1));\n                sessions[i] -= tasks[pos];\n            }\n        }\n        \n        return dp[key] = ans;\n    }\n    \n    int minSessions(vector<int>& tasks, int sessionTime) {\n        int n = tasks.size();\n        return solve(tasks, n, sessionTime, 0);\n    }\n};\n```\n\n
[]