LeetCode 1601: Maximum Number of Achievable Transfer Requests

Explanation:

To solve this problem, we need to find the maximum number of achievable requests where the net change in employee transfers is zero for each building. We can use backtracking to try all possible combinations of requests and keep track of the maximum achievable requests.

1. Initialize a counter to keep track of the maximum achievable requests.
2. Iterate through all possible combinations of requests using backtracking.
3. For each combination, check if the net change in employee transfers is zero for each building.
4. Update the counter with the maximum achievable requests found during the backtracking process.
5. Return the maximum achievable requests.

Time Complexity: O(2^n), where n is the number of requests. In the worst case, we need to try all possible combinations of requests.

Space Complexity: O(n), where n is the number of buildings.

:

class Solution {
    public int maximumRequests(int n, int[][] requests) {
        return backtrack(0, 0, new int[n], requests);
    }
    
    private int backtrack(int index, int count, int[] balance, int[][] requests) {
        if (index == requests.length) {
            for (int b : balance) {
                if (b != 0) return 0;
            }
            return count;
        }
        
        int take = 0, skip = 0;
        
        balance[requests[index][0]]--;
        balance[requests[index][1]]++;
        take = backtrack(index + 1, count + 1, balance, requests);

        balance[requests[index][0]]++;
        balance[requests[index][1]]--;
        skip = backtrack(index + 1, count, balance, requests);
        
        return Math.max(take, skip);
    }
}