C++ || DP + Bitmask || Recursion Memo BItmask ||
Idea is to create a mask (n bits) to track if ith task has been performed or not. \nIf not, then we have 2 choices : \n1. Pick it and perform it in current runn
Idea is to create a mask (n bits) to track if *ith* task has been performed or not. \nIf not, then we have 2 choices : \n1. Pick it and perform it in current running session : \n2. Pick it and create a new session to perform it : \n\nHere dp(mask, time) is the minimum number of sessions needed to finish all the tasks represented by mask. Mask will have some/all bits set which means that tasks at that index of set bit are already performed. \n\nRemaining code is easy to understand. Just simple memoization and bitmask.\n\n```\nclass Solution {\npublic:\n    int n;\n    int dp[16][1<<14];\n    int solve(vector<int>& tasks, int mask, int time, const int& sessionTime)\n    {\n        if(mask == 0) return 0;         // mask is zero means all tasks are finished\n        \n        if(dp[time][mask] != -1) return dp[time][mask];\n        \n        int ans = INT_MAX;\n        \n        for(int i=0; i<n; i++)\n        {\n            if((mask&(1<<i)))           // If ith task is available or not\n            {\n                if(time + tasks[i] <= sessionTime)        // If this task can be performed\n                    ans = min(ans, solve(tasks, (mask^(1<<i)), time+tasks[i], sessionTime));    // Mark this as completed in ongoing session\n                else  \n                    ans = min(ans, 1 + solve(tasks, (mask^(1<<i)), tasks[i], sessionTime)); // Mark this as completed and create a new session\n            }\n        }\n        return dp[time][mask] = ans;\n    }\n    \n    int minSessions(vector<int>& tasks, int sessionTime) {\n        n = tasks.size();\n        memset(dp, -1, sizeof(dp));\n        return solve(tasks, (1<<n)-1, 0, sessionTime) + 1;\n    }\n};\n```\n**Time: O(2^n * sessionTime * n) \nSpace: O(2^n * sessionTime)**
['Dynamic Programming', 'C', 'Bitmask']