# Maximum Number of Achievable Transfer Requests
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-number-of-achievable-transfer-requests)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-achievable-transfer-requests
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
---
## Problem
We have `n` buildings numbered from `0` to `n - 1`. Each building has a number of employees. It's transfer season, and some employees want to change the building they reside in.

You are given an array `requests` where `requests[i] = [fromi, toi]` represents an employee's request to transfer from building `fromi` to building `toi`.

**All buildings are full**, so a list of requests is achievable only if for each building, the **net change in employee transfers is zero**. This means the number of employees **leaving** is **equal** to the number of employees **moving in**. For example if `n = 3` and two employees are leaving building `0`, one is leaving building `1`, and one is leaving building `2`, there should be two employees moving to building `0`, one employee moving to building `1`, and one employee moving to building `2`.

Return _the maximum number of achievable requests_.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-number-of-achievable-transfer-requests/image0.jpg) 

**Input:** n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
**Output:** 5
**Explantion:** Let's see the requests:
From building 0 we have employees x and y and both want to move to building 1.
From building 1 we have employees a and b and they want to move to buildings 2 and 0 respectively.
From building 2 we have employee z and they want to move to building 0.
From building 3 we have employee c and they want to move to building 4.
From building 4 we don't have any requests.
We can achieve the requests of users x and b by swapping their places.
We can achieve the requests of users y, a and z by swapping the places in the 3 buildings.

**Example 2:**

![](https://assets.glich.co/dsa/maximum-number-of-achievable-transfer-requests/image1.jpg) 

**Input:** n = 3, requests = [[0,0],[1,2],[2,1]]
**Output:** 3
**Explantion:** Let's see the requests:
From building 0 we have employee x and they want to stay in the same building 0.
From building 1 we have employee y and they want to move to building 2.
From building 2 we have employee z and they want to move to building 1.
We can achieve all the requests. 

**Example 3:**

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

**Constraints:**

* `1 <= n <= 20`
* `1 <= requests.length <= 16`
* `requests[i].length == 2`
* `0 <= fromi, toi < n`

# Approaches
## Brute Force with Bitmasking
This approach explores every possible subset of the given transfer requests. Since the number of requests is small (up to 16), we can represent each subset using a bitmask. For each subset, we check if it's "achievable" by calculating the net change in employees for each building. If the net change is zero for all buildings, the subset is valid, and we update our maximum count.
**Time:** O(2^m * (m + n)), where `m` is the number of requests and `n` is the number of buildings. The outer loop runs `2^m` times. Inside, we iterate up to `m` times to build the balance array and `n` times to check it. · **Space:** O(n), where `n` is the number of buildings, required to store the `balance` array.
**Pros:** Conceptually simple and straightforward to implement.; Directly translates the problem of checking all subsets into code.
**Cons:** Inefficient due to re-calculating the balance for each of the `2^m` subsets from scratch.; The time complexity is exponential, making it unsuitable for a larger number of requests.
### Explanation
We iterate through all numbers from `0` to `2^m - 1`, where `m` is the total number of requests. Each number `i` in this range acts as a bitmask, representing a unique subset of requests.

If the `j`-th bit in the mask `i` is set, it signifies that the `j`-th request is included in the current subset.

For each mask, we perform the following steps:
1.  Create a `balance` array of size `n` (for `n` buildings), initialized to all zeros. This array will track the net flow of employees for each building.
2.  Count the number of requests in the current subset (which is the number of set bits in the mask).
3.  Iterate through the requests. For each request `[from, to]` included in the subset, we decrement `balance[from]` and increment `balance[to]`.
4.  After processing all requests in the subset, we check if all entries in the `balance` array are zero. This condition means that for every building, the number of employees leaving equals the number of employees arriving.
5.  If the balance condition is met, the subset is achievable. We then compare the size of this valid subset with our current maximum and update it if the current subset is larger.

After checking all `2^m` subsets, the maximum value found is the answer.

```java
class Solution {
    public int maximumRequests(int n, int[][] requests) {
        int m = requests.length;
        int maxAchievable = 0;

        for (int i = 0; i < (1 << m); i++) {
            int[] balance = new int[n];
            int currentRequests = 0;

            // Check which requests are in the current subset represented by 'i'
            for (int j = 0; j < m; j++) {
                if ((i & (1 << j)) != 0) {
                    int from = requests[j][0];
                    int to = requests[j][1];
                    balance[from]--;
                    balance[to]++;
                    currentRequests++;
                }
            }

            // Check if this subset is achievable
            boolean isAchievable = true;
            for (int k = 0; k < n; k++) {
                if (balance[k] != 0) {
                    isAchievable = false;
                    break;
                }
            }

            if (isAchievable) {
                maxAchievable = Math.max(maxAchievable, currentRequests);
            }
        }
        return maxAchievable;
    }
}
```
### Algorithm
- Initialize `maxAchievable = 0`.
- Let `m` be the number of requests.
- Loop through each integer `mask` from `0` to `2^m - 1`. Each `mask` represents a subset of requests.
- For each `mask`:
  - Initialize a `balance` array of size `n` to all zeros.
  - Initialize `subsetSize = 0`.
  - Iterate from `j = 0` to `m - 1`:
    - If the `j`-th bit is set in `mask`, it means `requests[j]` is in the subset.
    - Increment `subsetSize`.
    - Update the `balance` for `requests[j]`: decrement `balance` at the `from` index and increment at the `to` index.
  - After processing all requests in the subset, check if all elements in the `balance` array are zero.
  - If the balance condition is met, update `maxAchievable = max(maxAchievable, subsetSize)`.
- After checking all `2^m` masks, return `maxAchievable`.

## Backtracking
This approach uses recursion (backtracking) to explore all possible subsets of requests. It is more efficient than the pure brute-force method because it builds the state (the balance of employees per building) incrementally. At each step of the recursion, we decide whether to include the current request or not. This avoids recalculating the balance for each subset from scratch and allows for potential optimizations like pruning the search space.
**Time:** O(2^m * n). The recursion tree has `2^m` leaf nodes (representing all subsets). At each leaf, we perform an `O(n)` check on the balance array. The work at internal nodes is constant. · **Space:** O(m + n). `O(m)` for the recursion call stack depth and `O(n)` for the `balance` array.
**Pros:** More efficient than the bitmasking approach as it avoids recalculating the balance from scratch for every subset.; The recursive structure is a natural fit for subset enumeration problems.; Can be easily optimized with pruning techniques to cut off search paths that won't lead to a better solution.
**Cons:** Still has an exponential time complexity, making it infeasible for a large number of requests (`m`).; Recursive solutions can sometimes be harder to debug and may lead to stack overflow for very deep recursion (not an issue with `m <= 16`).
### Explanation
We define a recursive helper function, `backtrack(index, count)`, which explores subsets starting from `requests[index]`. The `count` parameter tracks the number of requests included in the current path. We use a `balance` array, passed through the recursion, to track the net change for each building.

The base case for the recursion is when `index` reaches the end of the `requests` array. At this point, we have a complete subset. We check if the `balance` array is all zeros. If it is, we've found an achievable combination of requests, and we update our global maximum with the current `count`.

In the recursive step for `requests[index]`, we explore two possibilities:
1.  **Exclude the request**: We don't include the current request in our subset and simply move to the next one by calling `backtrack(index + 1, count)`. The `balance` array remains unchanged.
2.  **Include the request**: We tentatively add the current request to our subset. We update the `balance` array for `requests[index]` (decrementing for the `from` building, incrementing for the `to` building) and then make a recursive call `backtrack(index + 1, count + 1)`.

After the recursive call for including the request returns, we must **backtrack** by reverting the changes made to the `balance` array. This is a critical step that ensures the `balance` array is in the correct state for other branches of the recursion.

The initial call to start the process is `backtrack(0, 0)` with a fresh balance array.

```java
class Solution {
    int maxAchievable = 0;

    public int maximumRequests(int n, int[][] requests) {
        int[] balance = new int[n];
        backtrack(0, 0, requests, balance);
        return maxAchievable;
    }

    private void backtrack(int index, int count, int[][] requests, int[] balance) {
        // Base case: we have processed all requests
        if (index == requests.length) {
            // Check if all buildings have a net change of 0
            for (int b : balance) {
                if (b != 0) {
                    return; // Not a valid state
                }
            }
            maxAchievable = Math.max(maxAchievable, count);
            return;
        }

        // --- Explore two choices for the current request ---

        // Choice 1: Exclude requests[index]
        backtrack(index + 1, count, requests, balance);

        // Choice 2: Include requests[index]
        int from = requests[index][0];
        int to = requests[index][1];
        
        balance[from]--;
        balance[to]++;
        
        backtrack(index + 1, count + 1, requests, balance);
        
        // Backtrack: undo the change for the next exploration path
        balance[from]++;
        balance[to]--;
    }
}
```
### Algorithm
- Initialize a global `maxAchievable = 0` and a `balance` array of size `n`.
- Define a recursive function `backtrack(index, count, requests, balance)`.
- **Base Case**: If `index` reaches `requests.length`:
  - Check if all elements in the `balance` array are zero.
  - If they are, it's a valid configuration. Update `maxAchievable = max(maxAchievable, count)`.
  - Return.
- **Recursive Step**: At `requests[index]`, explore two choices:
  - **1. Exclude `requests[index]`**: Make a recursive call `backtrack(index + 1, count, ...)`.
  - **2. Include `requests[index]`**:
    - Update the `balance` array based on the current request.
    - Make a recursive call `backtrack(index + 1, count + 1, ...)`.
    - **Crucially, revert the changes** made to the `balance` array to backtrack for other recursive paths.
- Start the process by calling `backtrack(0, 0, requests, new int[n])`.
- Return `maxAchievable`.

# Solutions
### CSharp

```csharp
public class Solution { private int m ; private int n ; private int [][] requests ; public int MaximumRequests ( int n , int [][] requests ) { m = requests . Length ; this . n = n ; this . requests = requests ; int ans = 0 ; for ( int mask = 0 ; mask < ( 1 << m ); ++ mask ) { int cnt = CountBits ( mask ); if ( ans < cnt && Check ( mask )) { ans = cnt ; } } return ans ; } private bool Check ( int mask ) { int [] cnt = new int [ n ]; for ( int i = 0 ; i < m ; ++ i ) { if ((( mask >> i ) & 1 ) == 1 ) { int f = requests [ i ][ 0 ], t = requests [ i ][ 1 ]; -- cnt [ f ]; ++ cnt [ t ]; } } foreach ( int v in cnt ) { if ( v != 0 ) { return false ; } } return true ; } private int CountBits ( int n ) { int count = 0 ; while ( n > 0 ) { n -= n & - n ; ++ count ; } return count ; } }
```

### Java

```java
class Solution {
private
  int m;
private
  int n;
private
  int[][] requests;
public
  int maximumRequests(int n, int[][] requests) {
    m = requests.length;
    this.n = n;
    this.requests = requests;
    int ans = 0;
    for (int mask = 0; mask < 1 << m; ++mask) {
      int cnt = Integer.bitCount(mask);
      if (ans < cnt && check(mask)) {
        ans = cnt;
      }
    }
    return ans;
  }
private
  boolean check(int mask) {
    int[] cnt = new int[n];
    for (int i = 0; i < m; ++i) {
      if ((mask >> i & 1) == 1) {
        int f = requests[i][0], t = requests[i][1];
        --cnt[f];
        ++cnt[t];
      }
    }
    for (int v : cnt) {
      if (v != 0) {
        return false;
      }
    }
    return true;
  }
}

```

### JavaScript

```javascript
/** * @param {number} n * @param {number[][]} requests * @return {number} */ var maximumRequests =
  function (n, requests) {
    const m = requests.length;
    let ans = 0;
    const check = (mask) => {
      const cnt = new Array(n).fill(0);
      for (let i = 0; i < m; ++i) {
        if ((mask >> i) & 1) {
          const [f, t] = requests[i];
          --cnt[f];
          ++cnt[t];
        }
      }
      return cnt.every((v) => v === 0);
    };
    for (let mask = 0; mask < 1 << m; ++mask) {
      const cnt = bitCount(mask);
      if (ans < cnt && check(mask)) {
        ans = cnt;
      }
    }
    return ans;
  };
function bitCount(i) {
  i = i - ((i >>> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
  i = (i + (i >>> 4)) & 0x0f0f0f0f;
  i = i + (i >>> 8);
  i = i + (i >>> 16);
  return i & 0x3f;
}

```

### CPP

```cpp
class Solution {
public:
  int maximumRequests(int n, vector<vector<int>> &requests) {
    int m = requests.size();
    int ans = 0;
    auto check = [&](int mask) -> bool {
      int cnt[n];
      memset(cnt, 0, sizeof(cnt));
      for (int i = 0; i < m; ++i) {
        if (mask >> i & 1) {
          int f = requests[i][0], t = requests[i][1];
          --cnt[f];
          ++cnt[t];
        }
      }
      for (int v : cnt) {
        if (v) {
          return false;
        }
      }
      return true;
    };
    for (int mask = 0; mask < 1 << m; ++mask) {
      int cnt = __builtin_popcount(mask);
      if (ans < cnt && check(mask)) {
        ans = cnt;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumRequests(self, n: int, requests: List[List[int]]) -> int: def check(mask: int) -> bool: cnt = [0] * n for i, (f, t) in enumerate(requests): if mask >> i & 1: cnt[f] -= 1 cnt[t] += 1 return all(v == 0 for v in cnt) ans = 0 for mask in range(1 << len(requests)): cnt = mask . bit_count() if ans < cnt and check(mask): ans = cnt return ans

```