Maximum Number of Achievable Transfer Requests

hard bitmask backtracking graph

Problem

There are n buildings and a list of transfer requests requests[i] = [from, to]. Pick a subset of requests so the net change in employees at every building is zero, maximizing the subset size.

Inputn = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]

Output5

Drop requests[3] or requests[5] (last one) — the remaining five form balanced cycles.

requests (e.g. 0,1;1,0;0,2)

def maximum_requests(n, requests):
    best = 0
    m = len(requests)
    for mask in range(1 << m):
        deg = [0] * n
        cnt = 0
        for i in range(m):
            if mask & (1 << i):
                u, v = requests[i]
                deg[u] -= 1
                deg[v] += 1
                cnt += 1
        if all(d == 0 for d in deg):
            best = max(best, cnt)
    return best

function maximumRequests(n, requests) {
  let best = 0;
  const m = requests.length;
  for (let mask = 0; mask < (1 << m); mask++) {
    const deg = new Array(n).fill(0);
    let cnt = 0;
    for (let i = 0; i < m; i++) {
      if (mask & (1 << i)) {
        deg[requests[i][0]]--; deg[requests[i][1]]++; cnt++;
      }
    }
    if (deg.every(d => d === 0)) best = Math.max(best, cnt);
  }
  return best;
}

class Solution {
    public int maximumRequests(int n, int[][] requests) {
        int best = 0, m = requests.length;
        for (int mask = 0; mask < (1 << m); mask++) {
            int[] deg = new int[n];
            int cnt = 0;
            for (int i = 0; i < m; i++) {
                if ((mask & (1 << i)) != 0) {
                    deg[requests[i][0]]--; deg[requests[i][1]]++; cnt++;
                }
            }
            boolean ok = true;
            for (int d : deg) if (d != 0) { ok = false; break; }
            if (ok) best = Math.max(best, cnt);
        }
        return best;
    }
}

int maximumRequests(int n, vector<vector<int>>& requests) {
    int best = 0, m = (int)requests.size();
    for (int mask = 0; mask < (1 << m); mask++) {
        vector<int> deg(n, 0);
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                deg[requests[i][0]]--; deg[requests[i][1]]++; cnt++;
            }
        }
        bool ok = true;
        for (int d : deg) if (d) { ok = false; break; }
        if (ok) best = max(best, cnt);
    }
    return best;
}

Explanation

Each request moves an employee from one building to another, and we may accept any subset of requests. The rule is that every building must end with the same number of employees it started with, and we want to accept as many requests as possible.

Since the number of requests m is small, we simply try every subset. The loop for mask in range(1 << m) walks through all 2^m subsets, where bit i of mask means "include request i."

For each chosen subset we compute a deg (net change) array per building: a request [u, v] does deg[u] -= 1 (one leaves) and deg[v] += 1 (one arrives). If every building's net change is zero, the subset is balanced and valid, so we update best with its size cnt.

Example: with requests forming cycles like 0→1, 1→0, those two cancel out and keep all degrees zero. Dropping a lone unmatched request like 3→4 lets the rest stay balanced, giving the maximum count.

Checking all subsets guarantees we never miss the largest balanced set.

Time: O(2^m · (m + n)) Space: O(n)