Maximum Number of Achievable Transfer Requests: Backtracking with Bitmask Enumeration

You are given n buildings numbered 0 to n - 1 and an array of transfer requests where requests[i] = [from_i, to_i] means an employee wants to transfer from building from_i to building to_i. You need to find the maximum number of requests you can approve such that the net change in the number of employees for every building is exactly zero.

This is LeetCode 1601: Maximum Number of Achievable Transfer Requests, and it is a great problem for learning how bitmask enumeration handles constrained subset selection. The constraint here is that every building must end up with the same number of employees as it started with. That means the approved requests must form a collection of cycles, where every person who leaves a building is replaced by someone arriving.

Why this problem matters

This problem teaches you a fundamental technique: enumerating all subsets of a small collection and checking a constraint on each one. The requests array can have at most 16 elements, which means there are at most 2^16 = 65,536 possible subsets. That is small enough to check every single one. Recognizing that the constraint size is small enough for brute-force subset enumeration is a skill that comes up repeatedly in competitive programming and interviews.

It also reinforces the connection between bitmasks and subsets. Each integer from 0 to 2^m - 1 (where m is the number of requests) represents a unique subset. Bit j being set means request j is included. This is the same idea behind Subsets, but applied to an optimization problem with a validity constraint rather than a pure enumeration problem.

Finally, the "net-zero" constraint introduces graph cycle thinking. A valid set of transfers must decompose into cycles in the building graph. You do not need to find the cycles explicitly, though. Instead, you just check that every building's in-degree equals its out-degree, which is equivalent to checking that the net change is zero for each building.

The key insight

Think of each request as a toggle: either you approve it or you do not. With m requests, there are 2^m possible subsets. For each subset, you compute the net change for every building. If building b appears as a "from" in k1 approved requests and as a "to" in k2 approved requests, its net change is k2 - k1. The subset is valid only when every building has a net change of zero.

The algorithm is:

1. Iterate through every bitmask from 0 to 2^m - 1.
2. For each bitmask, compute the net change array for all n buildings.
3. If every building's net change is zero, update the answer with the number of set bits (approved requests) in this mask.
4. Return the maximum count found.

You can also solve this with backtracking (recursively choosing to include or exclude each request), but the bitmask approach is cleaner and avoids recursion overhead. Both run in O(2^m * m) time.

The solution

def maximumRequests(n, requests):
    m = len(requests)
    best = 0

    for mask in range(1 << m):
        net = [0] * n
        count = 0

        for j in range(m):
            if mask & (1 << j):
                net[requests[j][0]] -= 1
                net[requests[j][1]] += 1
                count += 1

        if all(x == 0 for x in net):
            best = max(best, count)

    return best

Let's break this down.

The outer loop iterates through every possible subset of requests, encoded as an integer bitmask. For a bitmask mask, we check each bit position j. If bit j is set (mask & (1 << j) is nonzero), request j is included in the current subset.

For each included request [from, to], we decrement net[from] (one person leaves) and increment net[to] (one person arrives). The variable count tracks how many requests are in this subset.

After processing all bits, we check if the net array is all zeros. If it is, every building ends up with the same number of employees as it started, so this subset is valid. We update best with the count if it is larger than the current best.

The all(x == 0 for x in net) check is the key constraint. It ensures that the selected transfers form balanced cycles. Without this check, you could just approve every request, but that would leave some buildings overpopulated and others empty.

Visual walkthrough

Let's trace through the algorithm with n = 3 and requests = [[0,1],[1,0],[0,1],[1,2],[2,0]]. We have 5 requests, so there are 32 subsets to check. Watch how the net-zero constraint filters out invalid subsets and how the best valid subset uses all 5 requests.

Notice how the constraint is purely local: you compute the net change independently for each building. You do not need to trace cycles or build a graph explicitly. The net-zero check captures the cycle requirement implicitly. If every building has zero net change, the transfers must form one or more cycles.

Complexity analysis

Time: There are 2^m subsets. For each subset, we iterate through m bits to compute the net change array. The constraint check takes O(n) time, but since n is at most 20 and m is at most 16, the dominant factor is 2^m * m. With m = 16, that is about 1 million operations, which runs in well under a second.

Space: We use an array of size n for the net changes, plus a constant number of variables. The space does not depend on m except for storing the input.

The building blocks

1. Bitmask subset enumeration

The core technique is iterating through all 2^m integers and treating each integer as a subset. Bit j in mask k represents whether element j is in subset k. This is the same idea behind the iterative solution to Subsets, where you generate all subsets by iterating from 0 to 2^n - 1.

for mask in range(1 << m):
    for j in range(m):
        if mask & (1 << j):
            pass

This double loop is the skeleton. You plug in problem-specific logic inside the inner if block. For transfer requests, you update the net change array. For subset sum, you add the element to a running total. The pattern is always the same.

2. Net-zero balance check

The constraint that every building's net change must equal zero is equivalent to requiring that the approved requests decompose into directed cycles in the building graph. This is a useful reframing: instead of finding cycles (which is algorithmically harder), you just check a simple numerical property. This "balance check" pattern appears in many flow and matching problems.

Edge cases

• No valid subset except empty: If no non-empty subset of requests produces zero net change for all buildings, the answer is 0.
• Self-loops: A request [i, i] (someone transferring within the same building) contributes zero net change. It can always be included for free, so you should always approve self-loops. This can be used as an optimization: count self-loops first, remove them, then run bitmask enumeration on the remaining requests.
• All requests form one big cycle: For example, [[0,1],[1,2],[2,0]]. All requests can be approved. The answer equals the number of requests.
• Single building: If n = 1, every request is a self-loop [0, 0]. Approve all of them.
• m = 0: No requests means the answer is 0.

From understanding to recall

The pattern here is simple in concept: enumerate all subsets, check a constraint, track the best. But under interview pressure, the details matter. You need to remember the bit manipulation for checking if bit j is set, the net-change accounting (decrement from, increment to), and the all-zeros check.

Practice building the bitmask loop from scratch. Start with the outer for mask in range(1 << m) loop, then add the inner bit-check loop, then add the problem-specific logic. Once you can write the bitmask enumeration skeleton from memory, adapting it to any constraint-checking problem takes seconds.

The bitmask enumeration pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more efficient than grinding random problems and hoping the patterns stick.

Related posts

• Subsets - The foundational backtracking problem for generating all subsets. The bitmask approach used here is the iterative equivalent of the recursive subset generation.
• Combination Sum - Another backtracking problem that explores subsets with constraints. Compare the pruning approach there with the brute-force enumeration here.
• Permutations - Backtracking over orderings rather than subsets. Good contrast for understanding when you need permutations vs. subsets.

CodeBricks breaks Maximum Number of Achievable Transfer Requests into its bitmask enumeration building block, then drills it independently with spaced repetition. You type the subset enumeration skeleton from scratch until it is automatic. When a subset constraint problem shows up in your interview, you do not think about it. You just write it.