<p>There are <code>n</code> tasks assigned to you. The task times are represented as an integer array <code>tasks</code> of length <code>n</code>, where the <code>i<sup>th</sup></code> task takes <code>tasks[i]</code> hours to finish. A <strong>work session</strong> is when you work for <strong>at most</strong> <code>sessionTime</code> consecutive hours and then take a break.</p>

<p>You should finish the given tasks in a way that satisfies the following conditions:</p>

<ul>
	<li>If you start a task in a work session, you must complete it in the <strong>same</strong> work session.</li>
	<li>You can start a new task <strong>immediately</strong> after finishing the previous one.</li>
	<li>You may complete the tasks in <strong>any order</strong>.</li>
</ul>

<p>Given <code>tasks</code> and <code>sessionTime</code>, return <em>the <strong>minimum</strong> number of <strong>work sessions</strong> needed to finish all the tasks following the conditions above.</em></p>

<p>The tests are generated such that <code>sessionTime</code> is <strong>greater</strong> than or <strong>equal</strong> to the <strong>maximum</strong> element in <code>tasks[i]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> tasks = [1,2,3], sessionTime = 3
<strong>Output:</strong> 2
<strong>Explanation:</strong> You can finish the tasks in two work sessions.
- First work session: finish the first and the second tasks in 1 + 2 = 3 hours.
- Second work session: finish the third task in 3 hours.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> tasks = [3,1,3,1,1], sessionTime = 8
<strong>Output:</strong> 2
<strong>Explanation:</strong> You can finish the tasks in two work sessions.
- First work session: finish all the tasks except the last one in 3 + 1 + 3 + 1 = 8 hours.
- Second work session: finish the last task in 1 hour.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> tasks = [1,2,3,4,5], sessionTime = 15
<strong>Output:</strong> 1
<strong>Explanation:</strong> You can finish all the tasks in one work session.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == tasks.length</code></li>
	<li><code>1 &lt;= n &lt;= 14</code></li>
	<li><code>1 &lt;= tasks[i] &lt;= 10</code></li>
	<li><code>max(tasks[i]) &lt;= sessionTime &lt;= 15</code></li>
</ul>

class Solution:
  def minSessions(self, arr: List[int], sessionTime: int) -> int:
    n = len(arr)

    # Sort in decreasing order.
    arr.sort(reverse=True)
    dp = {}
    done_mask = (1 << n) - 1

    # i is the item id, gid is the group id.
    def backtrack(i, gid, cur_sum, mask):
      if mask == done_mask:
        # Note: check cur_sum.
        if cur_sum > 0:
          return 1
        return 0

      # No need to update cache for this condition. Simply return the answer that will never be
      # adopted by its parent caller. E.g., for getting min, return math.inf.
      if i >= len(arr):
        return math.inf

      state = (mask, cur_sum)
      if state in dp:
        return dp[state]

      res = math.inf
      # Option 1: skip the current item index.
      tmp = backtrack(i + 1, gid, cur_sum, mask)
      res = min(res, tmp)

      # If the current item is already taken, skip the following options.
      if mask & (1 << i) != 0:
        dp[state] = res
        return dp[state]

      next_mask = (mask | (1 << i))
      # Option 2: go to the next group. Reset cur_sum and curnum_id.
      if cur_sum + arr[i] > sessionTime:
        tmp = 1 + backtrack(0, gid + 1, arr[i], next_mask)
        res = min(res, tmp)
      # Option 3: add to the current group.
      else:
        tmp = backtrack(i + 1, gid, cur_sum + arr[i], next_mask)
        res = min(res, tmp)
      dp[state] = res
      return dp[state]

    return backtrack(0, 0, 0, 0)
3491