[Python] dynamic programming on subsets, explained
You can see that in this problem n <= 14, so we need to apply some kind of bruteforce algorithm. If we try just n! options, it will be too big, so the idea is t
You can see that in this problem `n <= 14`, so we need to apply some kind of bruteforce algorithm. If we try just `n!` options, it will be too big, so the idea is to use dynamic programming on subsets. Let `dp(mask)`, where `mask` is bitmask of already used jobs be the tuple of numbers: first one is number of sessions we took so far and the second one is how much time we spend for the last session.\n\nTo calculate `dp(mask)`, let us say `dp(10110)`, we need to look at all places we have `0`, that is `1-th, 2-th, 4-th` and look at positions `dp(00110), dp(10010), dp(10100)`. We calculate `full = last + tasks[j] > T` is indicator that last session is full and we need to start new one. So, total number of sessions we have is `pieces + full` and what we have in the last session is `tasks[j]` if session is full: we start new one and `tasks[j] + last` if it is not full.\n\n#### Complexity\nTime complexity is `O(2^n * n)`, because we have `2^n` masks and `O(n)` transitions from given mask. Space complexity is `O(2^n)`.\n\n```python\nclass Solution:\n    def minSessions(self, tasks, T):\n        n = len(tasks)\n\n        @lru_cache(None)\n        def dp(mask):\n            if mask == 0: return (1, 0)\n            ans = (float("inf"), float("inf"))\n            for j in range(n):\n                if mask & (1<<j):\n                    pieces, last = dp(mask - (1 << j))\n                    full = (last + tasks[j] > T)\n                    ans = min(ans, (pieces + full, tasks[j] + (1-full)*last))  \n            return ans\n\n        return dp((1<<n) - 1)[0]\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Dynamic Programming', 'Bitmask']