Parallel Courses II: Bitmask DP for Course Scheduling

You are given n courses labeled from 1 to n, a list of prerequisite pairs relations where [x, y] means you must take course x before course y, and an integer k representing the maximum number of courses you can take in a single semester. You can only take a course if you have completed all its prerequisites in previous semesters. Return the minimum number of semesters needed to take all n courses.

This is LeetCode 1494: Parallel Courses II, and it is significantly harder than the original Parallel Courses problem. The twist is the constraint k, which limits how many courses you can take per semester. That constraint turns a simple topological sort into an NP-hard scheduling problem.

Why this problem matters

Course scheduling with a concurrency limit is a classic NP-hard problem. In the general case, finding the optimal schedule is computationally intractable. But LeetCode gives us a crucial constraint: n is at most 15. That small upper bound is the signal that bitmask DP is the intended approach.

Bitmask DP lets you represent states as integers where each bit corresponds to whether a particular item has been selected or not. With n up to 15, the total number of states is 2^15 = 32768, which is very manageable. This technique shows up in many hard problems where you need to track subsets: traveling salesman, assignment problems, and set cover variants.

Understanding this problem deepens your ability to recognize when bitmask DP applies. The pattern is consistent: small n (usually 15 to 20), a need to track which elements have been "used" or "visited", and transitions that depend on the current subset.

The key insight

Since n is at most 15, you can represent the set of completed courses as a single integer (bitmask). Bit i being set means course i has been taken. The DP state is this bitmask, and dp[mask] stores the minimum number of semesters to reach that state.

For each state, you first figure out which courses are available: a course is available if it is not yet taken and all its prerequisites are in the current mask. Then you try all subsets of the available courses that have at most k elements. Each valid subset represents a possible semester. You transition to the new state by OR-ing the subset into the current mask and updating the DP value.

The trick for efficiently enumerating subsets of a bitmask is the classic sub = (sub - 1) & available iteration. This visits every non-empty subset of available in decreasing order, skipping values that are not subsets.

The solution

def minNumberOfSemesters(n, relations, k):
    prereq = [0] * n
    for u, v in relations:
        prereq[v - 1] |= 1 << (u - 1)

    dp = [n] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        if dp[mask] == n:
            continue
        available = 0
        for i in range(n):
            if not (mask & (1 << i)) and (mask & prereq[i]) == prereq[i]:
                available |= 1 << i

        sub = available
        while sub:
            if bin(sub).count("1") <= k:
                dp[mask | sub] = min(dp[mask | sub], dp[mask] + 1)
            sub = (sub - 1) & available

    return dp[(1 << n) - 1]

Let's break this down piece by piece.

Prerequisite encoding. For each course v, prereq[v-1] is a bitmask where bit u-1 is set for every prerequisite u. This lets you check "are all prerequisites met?" with a single bitwise AND: (mask & prereq[i]) == prereq[i].

DP initialization. dp[0] = 0 means zero semesters needed when no courses are taken. All other states start at n (an upper bound, since you can always take one course per semester).

Finding available courses. For each untaken course i, check two conditions: bit i is not set in mask (not yet taken), and all prerequisite bits are set in mask. If both hold, set bit i in available.

Subset enumeration. The while sub loop with sub = (sub - 1) & available iterates through every non-empty subset of available. For each subset with at most k bits set, update the DP.

Answer. dp[(1 << n) - 1] is the answer: the minimum semesters to reach the state where all n courses are taken.

Visual walkthrough

The walkthrough above uses n=4, relations=[[1,2],[1,3],[2,4]], and k=2. Notice how the algorithm explores all valid subsets of available courses at each step. When multiple courses are available and k allows taking several at once, the algorithm considers every combination to find the schedule that minimizes total semesters.

Complexity analysis

Time: O(3^n). This might seem surprising, but it comes from a well-known identity. For each of the 2^n masks, we enumerate all subsets of the available courses. The total work across all masks is the sum of 2^popcount(available) for each mask. By the binomial theorem, summing 2^k * C(n,k) for k from 0 to n gives 3^n. With n=15, that is about 14 million operations, which is fast enough.

Space: O(2^n). The DP array has 2^n entries. With n=15, that is 32768 integers.

The building blocks

1. Prerequisite encoding with bitmasks

prereq = [0] * n
for u, v in relations:
    prereq[v - 1] |= 1 << (u - 1)

Each course's prerequisites are packed into a single integer. To check if all prerequisites of course i are satisfied by the current state mask, you compute (mask & prereq[i]) == prereq[i]. This is an O(1) operation instead of iterating through a list of prerequisites. The bitmask representation is what makes the entire DP efficient.

2. Subset enumeration

sub = available
while sub:
    if bin(sub).count("1") <= k:
        dp[mask | sub] = min(dp[mask | sub], dp[mask] + 1)
    sub = (sub - 1) & available

The expression (sub - 1) & available is the standard way to iterate through all non-empty subsets of a bitmask. Here is why it works: subtracting 1 from sub flips the lowest set bit and sets all lower bits. AND-ing with available ensures we only keep bits that are in the original set. This effectively "counts down" through all subsets. When sub reaches 0, the loop ends.

Edge cases

• No prerequisites. All courses are independent. You can take k per semester, so the answer is ceil(n / k). The DP handles this naturally since all courses are available from the start.
• Chain of courses. Every course depends on the previous one: 1 -> 2 -> 3 -> ... -> n. You can only take one course per semester regardless of k, so the answer is n.
• k equals n. You can take all available courses every semester. This reduces to finding the longest chain in the prerequisite graph (the critical path).
• k equals 1. You take exactly one course per semester. The answer is always n, regardless of the prerequisite structure.
• All courses independent. No edges in the graph. Same as the "no prerequisites" case. Answer is ceil(n / k).
• Diamond dependency. Course 1 is a prerequisite for courses 2 and 3, and both 2 and 3 are prerequisites for course 4. With k=2, you take in semester 1, in semester 2, and in semester 3. The DP explores taking or alone versus both together and finds the optimal.

From understanding to recall

The hardest part of this problem is not the algorithm itself, but remembering all the pieces under pressure. You need to encode prerequisites as bitmasks, write the DP loop, compute available courses with bitwise AND, enumerate subsets with the (sub-1) & available trick, and check the popcount constraint. That is a lot of moving parts.

Practice building the solution in phases. First, write the prerequisite encoding. Second, write the main DP loop with the availability check. Third, add the subset enumeration. Each phase is a self-contained building block. Once you can write each phase from memory without hesitation, combining them becomes natural.

Related posts

• Course Schedule - Topological sort for prerequisite cycle detection
• Course Schedule II - Finding a valid course order with topological sort
• Partition to K Equal Sum Subsets - Another bitmask DP problem that tracks subsets

Parallel Courses II is a beautiful example of how a small constraint on n opens the door to bitmask DP. The prerequisite encoding, the available-course computation, and the subset enumeration are three distinct building blocks that you can drill independently. When you can reconstruct each one from scratch, the full solution comes together smoothly.