<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, tasks: List[int], sessionTime: int) -> int:  
        # Calculate the number of tasks.
        num_tasks = len(tasks)
      
        # Initialize a list of booleans to keep track of which combinations of tasks
        # can fit into a single session.
        can_fit_session = [False] * (1 << num_tasks)
      
        # Check all combinations of tasks.
        for mask in range(1, 1 << num_tasks):
            # Calculate the total time of tasks in the current combination.
            total_time = sum(tasks[j] for j in range(num_tasks) if mask >> j & 1)
          
            # Set True in can_fit_session if the total time of tasks is within the sessionTime.
            can_fit_session[mask] = total_time <= sessionTime
      
        # Initialize an array to store the minimum sessions needed for every task combination.
        min_sessions_needed = [inf] * (1 << num_tasks)
        # Base case: zero tasks require zero sessions.
        min_sessions_needed[0] = 0

        # Calculate the minimum sessions required for all the combinations.
        for mask in range(1, 1 << num_tasks):
            # Store the current mask to iterate over its subsets.
            subset = mask
            # Iterate over all the subsets of the mask.
            while subset:
                # Check if the current subset can fit into one session.
                if can_fit_session[subset]:
                    # Update the minimum sessions needed if we can achieve a smaller number.
                    min_sessions_needed[mask] = min(min_sessions_needed[mask], min_sessions_needed[mask ^ subset] + 1)
                # Move to the next subset.
                subset = (subset - 1) & mask
      
        # Return the minimum sessions needed for all tasks.
        return min_sessions_needed[-1]

        def backtrack(idx):
            nonlocal ans           
            if len(combo) >= ans:
                return
            if idx == len(tasks):
                ans = min(ans, len(combo))
                return
            for i in range(len(combo)):
                if tasks[idx] + combo[i] <= sessionTime:
                    combo[i] += tasks[idx]
                    backtrack(idx + 1)
                    combo[i] -= tasks[idx]
            combo.append(tasks[idx])
            backtrack(idx + 1)
            combo.pop()
        
        ans = len(tasks)
        combo = []        
        tasks.sort(reverse=True)
        backtrack(0)
        return ans


        subsets = []
        self.ans = len(tasks)        
        def func(idx):
            if len(subsets) >= self.ans:
                return
            
            if idx == len(tasks):
                self.ans = min(self.ans, len(subsets))
                return
            
            for i in range(len(subsets)):
                if subsets[i] + tasks[idx] <= sessionTime:
                    subsets[i] += tasks[idx]
                    print(subsets, 'inner')
                    func(idx + 1)
                    subsets[i] -= tasks[idx]
            print(subsets)
            subsets.append(tasks[idx])
            func(idx + 1)
            subsets.pop()
        
        func(0)
        return self.ans

        tasks.sort(reverse=True)        
        n = len(tasks)
        visited = [False] * n        
        i, cnt = 0, 0
        print(tasks)
        while i < n:            
            # k = i            
            if visited[i] is True:
                i += 1
                continue
            time = 0
            for k in range(i, n):
                if visited[k] is False and time + tasks[k] <= sessionTime:
                    time += tasks[k]
                    visited[k] = True
            print(visited)
            if time == 0:
                break
            cnt += 1
            i += 1
        return cnt

        # tasks.sort(reverse=True)
        # n = len(tasks)
        # i, j = 0, n - 1
        # cnt = 0
        # # print(tasks)
        # while i <= j:            
        #     k = i            
        #     time = 0
        #     while k <= j and time + tasks[k] <= sessionTime:
        #         time += tasks[k]
        #         k += 1
        #     while j >= k and time + tasks[j] <= sessionTime:
        #         time += tasks[j]
        #         j -= 1
        #     # print(k, j, time)
        #     cnt += 1
        #     i = k
        # return cnt
3852