Get started

Maximum Number of Achievable Transfer Requests — Hard Problem & Solution

There are n buildings, numbered 0 to n - 1, and every building is full.

Problem statement

There are n buildings, numbered 0 to n - 1, and every building is full. Each requests[i] = [from, to] is an employee asking to move from building from to building to (possibly the same building).

You may approve any subset of the requests, but because the buildings are full, the approved set must leave every building's headcount unchanged: for each building, the number of approved employees leaving it equals the number of approved employees arriving.

Return the maximum number of requests you can approve.

Example 1

Input: n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
Output: 5
Explanation: Approve every request except `[3,4]`: buildings 0, 1 and 2 each lose and gain the same number of people.

Example 2

Input: n = 3, requests = [[0,0],[1,2],[2,1]]
Output: 3

Example 3

Input: n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]
Output: 4
Explanation: The four moves form one cycle.

Constraints

  • 1 <= n <= 20
  • 1 <= requests.length <= 16
  • requests[i].length == 2
  • 0 <= from_i, to_i < n

How to solve Maximum Number of Achievable Transfer Requests

With at most 16 requests, enumerate every subset — by backtracking over take/skip decisions with an incrementally maintained balance per building — and keep the largest balanced one.

Approach

  1. Keep delta[b] for each building, all zero at the start.
  2. dfs(i, taken): if i == len(requests), update the answer with taken when every delta is zero.
  3. If taken + (remaining requests) <= best, return early.
  4. Take request i (delta[from]--, delta[to]++, recurse with taken + 1, undo), then skip it (recurse with taken).

Why it works

A set of approved moves keeps every building full exactly when each building's departures equal its arrivals, i.e. all net changes are zero. The search inspects every subset that could still beat the current best, so it finds the maximum.

Complexity

  • Time — O(2^m · n) for m requests
  • Space — O(n + m)

Pitfalls

  • A request from a building to itself is always approvable — it never changes the balance.
  • Checking only that the total balance is zero is not enough; every building must balance on its own.
  • Skipping the bound is fine for correctness but much slower.

Reference solution

Python

from typing import List

def maximumRequests(n: int, requests: List[List[int]]) -> int:
    m = len(requests)
    delta = [0] * n
    best = [0]

    def dfs(i, taken):
        if i == m:
            if taken > best[0] and all(d == 0 for d in delta):
                best[0] = taken
            return
        if taken + (m - i) <= best[0]:
            return
        a, b = requests[i]
        delta[a] -= 1
        delta[b] += 1
        dfs(i + 1, taken + 1)
        delta[a] += 1
        delta[b] -= 1
        dfs(i + 1, taken)

    dfs(0, 0)
    return best[0]

JavaScript

var maximumRequests = function(n, requests) {
    var m = requests.length;
    var delta = new Array(n).fill(0);
    var best = 0;
    var dfs = function(i, taken) {
        if (i === m) {
            if (taken > best) {
                for (var b = 0; b < n; b++) if (delta[b] !== 0) return;
                best = taken;
            }
            return;
        }
        if (taken + (m - i) <= best) return;
        var from = requests[i][0], to = requests[i][1];
        delta[from]--;
        delta[to]++;
        dfs(i + 1, taken + 1);
        delta[from]++;
        delta[to]--;
        dfs(i + 1, taken);
    };
    dfs(0, 0);
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Bit Manipulation