Bit Mask DP | C++ Solution |
Intution\n1. We can Solve this question with Recusion ( But it Takes a lot higher time) (Generally T.C. -> O( N ! * N))\n2. In Recursive Solution of such type o
**Intution**\n1. We can Solve this question with Recusion ( But it Takes a lot higher time) (Generally T.C. -> O( N ! * N))\n2. In Recursive Solution of such type of Problems, we need to modify the original array OR take a **Visited array**  to Remember wich indices are visited.\n3. so essentially the if we wanna memoize the state of Recursion, It needs a **Map(which memoizes values for each a visited array)** (T.C. Slightly Reduces) (still -TLE May Come ).\n\n**NOTE**\n1. If the size of array (n<=22) we can mark visited indices in the first \'n\' bits of  a mask (Integer) Instead of visited array.\n2. Which gives a lot quicker access, This is essentially The BIT_MASK DP.\n3. ** STORING THE VISITED INDICES IN THE BITS OF INREGER ** ( Which Represents the State).\n\n```\nclass Solution {\npublic:\n    int mx;\n    int dp[1<<14][16];\n    int solve(int wd,int time ,vector<int>& tasks,int idx){\n        int n=tasks.size();        \n        if(idx==n){\n            return time<mx;\n        }\n        if(dp[wd][time]!=-1)return dp[wd][time];\n        int ans=INT_MAX;\n        for(int i=0;i<n;i++){\n            if((wd & (1<<i))){\n                // wd[i]=true;\n                wd=wd ^ (1<<i);\n                if(tasks[i]>time){\n                    int curr=1+solve(wd,mx-tasks[i],tasks,idx+1);\n                    ans=min(ans,curr);\n                }else if(tasks[i]==time){\n                    ans=min(ans,1+solve(wd,mx,tasks,idx+1));\n                }else{\n                    ans=min(ans,solve(wd,time-tasks[i],tasks,idx+1));\n                }\n                wd=wd ^ (1<<i);\n            }\n        }\n        return dp[wd][time]=ans;\n    }\n    int minSessions(vector<int>& tasks, int sessionTime) {\n        int n=tasks.size();\n        // vector<bool> workdone(n,0);\n        int workdone=1<<n;\n        workdone--;\n        mx=sessionTime;\n        memset(dp,-1,sizeof(dp));\n        return solve(workdone,sessionTime,tasks,0);\n    }\n};\n```
['Dynamic Programming', 'Bitmask']