Minimum Number of Work Sessions to Finish the Tasks

MediumDP · Bitmask over Subsets🧩 Bitmask DP LeetCode #1986 ↗Updated Oct 30, 2026

Problem

Task i takes tasks[i] hours. You work in sessions of at most sessionTime consecutive hours; a task started in a session must finish in that same session, and you may do the tasks in any order. Return the minimum number of sessions needed to finish every task.

Inputtasks=[4,2,3,1], sessionTime=5Output2 ({4,1} and {2,3})

Inputtasks=[5,5,5], sessionTime=5Output3

Inputtasks=[1,1,1,1], sessionTime=10Output1

1 ≤ n ≤ 14 · 1 ≤ tasks[i] ≤ 10 · max(tasks) ≤ sessionTime ≤ 15

Try it yourself

Java

class Solution {
    public int minSessions(int[] tasks, int sessionTime) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

n ≤ 14 screams bitmask over subsets. Better still, process masks in increasing order and keep, for each set of finished tasks, the lexicographically smallest pair (sessions used, hours in the last session) — fewer sessions first, then the emptiest open session.

PatternBitmask DP

Instinct n is tiny (about 20 or less) and you must use, visit or assign every item - make the set of used items a bitmask and DP over all 2^n subsets.

Memory hack Small n, big choice - let the bits keep score: each item is a light switch and the mask is the whole switch panel.

Open the Bitmask DP guide →

Approaches

Brute ForceBacktracking into Open Sessions

Time O(n!)Space O(n)

Place tasks one by one: put task i into any already-open session with room, or open a new one. Every grouping is reachable, so the minimum over all leaves is the answer; branches that already use as many sessions as the best known answer are cut.

Java

private int best;

public int minSessions(int[] tasks, int sessionTime) {
    best = tasks.length; // one task per session always works
    place(tasks, 0, new int[tasks.length], 0, sessionTime);
    return best;
}

private void place(int[] tasks, int i, int[] load, int open, int cap) {
    if (open >= best) return; // cannot beat the best answer anymore
    if (i == tasks.length) {
        best = open;
        return;
    }
    for (int s = 0; s < open; s++) {
        if (load[s] + tasks[i] <= cap) {
            load[s] += tasks[i];
            place(tasks, i + 1, load, open, cap);
            load[s] -= tasks[i];
        }
    }
    load[open] = tasks[i]; // start a new session
    place(tasks, i + 1, load, open + 1, cap);
    load[open] = 0;
}

Exhaustive and intuitive (bin packing), but worst-case exponential with a large base.

BetterSubset DP: Peel Off One Full Session

Time O(3ⁿ)Space O(2ⁿ)

dp[mask] = fewest sessions for the tasks in mask. Some session in an optimal plan holds a subset sub of mask whose total fits, so dp[mask] = min(dp[mask ^ sub] + 1) over all fitting submasks. Enumerating submasks of every mask costs 3ⁿ in total.

Java

public int minSessions(int[] tasks, int sessionTime) {
    int n = tasks.length, full = 1 << n;
    int[] sum = new int[full];
    for (int mask = 1; mask < full; mask++) {
        int low = Integer.numberOfTrailingZeros(mask);
        sum[mask] = sum[mask & (mask - 1)] + tasks[low];
    }
    int[] dp = new int[full];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int mask = 1; mask < full; mask++) {
        // walk every non-empty submask of mask
        for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
            if (sum[sub] <= sessionTime && dp[mask ^ sub] + 1 < dp[mask])
                dp[mask] = dp[mask ^ sub] + 1;
        }
    }
    return dp[full - 1];
}

Polynomial in 2ⁿ, but 3¹⁴ ≈ 4.8M submask checks.

OptimalBitmask DP with (Sessions, Last Load) Pairs

Time O(n · 2ⁿ)Space O(2ⁿ)

Build plans by adding one task at a time to the current session, or opening a new one when it doesn't fit. For each mask keep the best pair (cnt, load): fewer sessions always wins, and with equal sessions a lighter last session can absorb at least as much. Any optimal grouping can be produced by finishing sessions one after another, so this is exact.

Java

public int minSessions(int[] tasks, int sessionTime) {
    int n = tasks.length, full = 1 << n;
    int[] cnt = new int[full];  // sessions used, counting the open one
    int[] load = new int[full]; // hours already in the open session
    Arrays.fill(cnt, Integer.MAX_VALUE);
    cnt[0] = 1;
    for (int mask = 0; mask < full; mask++) {
        for (int i = 0; i < n; i++) {
            if ((mask >> i & 1) == 1) continue;
            int c = cnt[mask], l = load[mask] + tasks[i];
            if (l > sessionTime) { // does not fit: open a fresh session
                c++;
                l = tasks[i];
            }
            int next = mask | 1 << i;
            if (c < cnt[next] || (c == cnt[next] && l < load[next])) {
                cnt[next] = c;
                load[next] = l;
            }
        }
    }
    return cnt[full - 1];
}

Only n transitions per mask — the tightest standard solution.

Pro tip

The same “(count, last load)” trick solves elevator/bin packing with n ≤ 20, where 3ⁿ would be far too slow.

At a glance

Level	Approach	Time	Space
Brute Force	Backtracking into Open Sessions	`O(n!)`	`O(n)`
Better	Subset DP: Peel Off One Full Session	`O(3ⁿ)`	`O(2ⁿ)`
Optimal	Bitmask DP with (Sessions, Last Load) Pairs	`O(n · 2ⁿ)`	`O(2ⁿ)`

Common pitfalls

Greedy (sort descending, first fit) is not always optimal — it's bin packing.
Comparing only session counts and ignoring the open session's load in the optimal DP.
Submask loop sub = (sub - 1) & mask must stop at 0, or it spins forever.

Interview tips

Point at n ≤ 14 and say “this is a bitmask DP” before anything else.
Offer the 3ⁿ submask DP first; it's easy to prove correct.
Then upgrade to the pair DP and justify the tie-break on the open session's load.

Pattern

Bitmask DP → partition or order a tiny set (n ≤ 20) where the state is “which items are done”.

My notes saved in this browser