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 looks a lot like bin packing: fit items into bins of fixed capacity, minimize the number of bins used. The key wrinkle is that n is at most 14, which is small enough for exponential approaches but too large for factorial ones to be efficient.

The constraint n <= 14 is a huge hint. With 14 items, we have 2^14 = 16,384 possible subsets. That's a very comfortable number for bitmask-based techniques. The core observation is that we can represent which tasks have been completed as a bitmask, and for each state, we care about how many sessions we've used and how much time remains in the current session.

Key Constraints:

Intuition

The most natural way to think about this: try placing each task into an existing session (if it fits) or start a new session. This is essentially the bin packing problem solved via backtracking.

We maintain a list of sessions, each with its current total time. For each task, we try to add it to each existing session where it fits, or we open a new session. We track the minimum number of sessions across all valid arrangements.

To make this practical, we need pruning. If we've already found a solution with k sessions, we can skip any branch that already uses k or more sessions. Sorting tasks in descending order also helps, since placing large tasks first reduces the branching factor early.

Algorithm

Example Walkthrough

Code

The backtracking approach explores a massive decision tree, repeatedly solving the same subproblem for different orderings. What if we could remember the result for each unique "which tasks are left" state using a bitmask?

Intuition

With n <= 14, we can represent the set of completed tasks as a bitmask. If bit i is set, task i has been completed. There are only 2^14 = 16,384 possible states.

But which tasks are done isn't the full story. We also need to know how much time remains in the current session, because that determines whether the next task we pick fits in the current session or forces us to open a new one.

So our DP state is dp[mask], storing a pair: (number of sessions used, remaining time in the current session). We pack both values into a single integer where sessions occupy the high bits and remaining time occupies the low bits. This way, standard min() comparison prioritizes fewer sessions, which is our optimization target.

Algorithm

Example Walkthrough

Code

The O(n * 2^n) approach is already fast, but there's an alternative that some interviewers prefer: precompute which subsets fit in a single session, then use subset enumeration DP to partition tasks into the fewest valid groups.

Intuition

Instead of adding tasks one at a time, let's think at a higher level. First, figure out all subsets of tasks that can fit in a single session. Then, the problem becomes: partition the full set of tasks into the fewest number of valid subsets.

We define dp[mask] as the minimum number of sessions to complete exactly the tasks in mask. For every valid subset sub of mask (where the tasks in sub fit in one session), we have dp[mask] = min(dp[mask], dp[mask ^ sub] + 1).

The trick to enumerating all subsets of a mask efficiently is a classic bit manipulation technique: start from sub = mask, then repeatedly compute sub = (sub - 1) & mask until sub becomes 0. This enumerates all subsets without redundancy and runs in O(3^n) total across all masks.

Algorithm

Example Walkthrough

Code