We need to partition tasks into groups (sessions), where the sum of task times in each group is at most sessionTime, and we want to minimize the number of groups.

This is the bin packing problem: fit items into bins of fixed capacity, minimize the number of bins used. Bin packing is NP-hard in general, so there is no known polynomial algorithm. What makes this version tractable is that n is at most 14, small enough for exponential algorithms to run quickly but too large for brute-force factorial enumeration of all orderings.

With 14 items there are 2^14 = 16,384 possible subsets, a count small enough to store in an array and iterate over. That points to a bitmask approach: represent the set of completed tasks as a bitmask, and for each state track how many sessions have been used and how much time remains in the current session.

Key Constraints

Intuition

Process tasks one at a time. For each task, either place it into an existing session that still has room, or open a new session for it. Exploring every such choice with backtracking covers all possible assignments of tasks to sessions.

We maintain a list of sessions, each holding its current total time. For each task we try adding it to each existing session where it fits, and we also try opening a new session. We track the minimum session count across all valid arrangements.

Two optimizations keep this from exploring the full search space. First, prune: once we have a solution using best sessions, any branch that already uses best or more sessions cannot improve the answer, so we stop. Second, sort tasks in descending order. Placing large tasks first fills sessions faster, which raises the session count earlier and lets the prune cut branches sooner.

Algorithm

Example Walkthrough

Code

Backtracking re-explores the same set of completed tasks many times, once for every order in which those tasks could have been placed. The next approach removes that repetition by keying a DP table on the set of completed tasks, represented as a bitmask.

Intuition

With n <= 14, the set of completed tasks fits in a bitmask: if bit i is set, task i is done. There are 2^14 = 16,384 such states.

The set of completed tasks alone is not enough to decide the next move. We also need to know the current session's load, since that determines whether the next task fits in the current session or forces a new one. So the DP state is dp[mask] holding a pair: the number of sessions used and the time already used in the current session.

To compare two states with a single min() call, both values are packed into one integer: (sessions << 16) | used, where used is the time consumed in the current session. Sessions occupy the high bits and used time the low bits, so a smaller packed value means fewer sessions first, and among equal session counts, less time used. Less time used means more time remaining, the state we want to keep among ties. The remaining time at any point is sessionTime - used. The Python version stores the equivalent pair (sessions, -remaining) and relies on tuple comparison, which orders the same way.

Algorithm

Example Walkthrough

Code

The O(n * 2^n) approach runs well within limits. A different DP formulation works at the level of whole sessions rather than one task at a time: precompute which subsets fit in a single session, then partition the full task set into the fewest such subsets.

Intuition

This approach works at the session level instead of the task level. Each session is one valid subset of tasks (one whose total time is at most sessionTime), and the answer is the smallest number of such subsets that partition all the tasks.

Define dp[mask] as the minimum number of sessions to complete exactly the tasks in mask. To build dp[mask], choose one subset sub of mask to be the last session. If the tasks in sub fit in one session, the rest (mask ^ sub) is solved recursively: dp[mask] = min(dp[mask], dp[mask ^ sub] + 1). Trying every valid sub as the final session covers all partitions.

Enumerating every subset of a mask uses a standard bit manipulation loop: start from sub = mask, then repeatedly compute sub = (sub - 1) & mask until sub reaches 0. This visits each subset of mask exactly once. Summed over all masks, the total number of (mask, sub) pairs is 3^n, since each bit is independently in sub, in mask but not sub, or outside mask.

Algorithm

Example Walkthrough

Code