## Maximum Number of Achievable Transfer Requests

• Time:O(n \cdot 2^|\texttt{requests}|)
• Space:O(n + |\texttt{requests}|)

## C++

class Solution {
public:
int maximumRequests(int n, vector<vector<int>>& requests) {
int ans = 0;
vector<int> degree(n);  // degree[i] := degree of building i

function<void(int, int)> dfs = [&](int i, int processedReqs) {
if (i == requests.size()) {
if (all_of(begin(degree), end(degree), [](int d) { return d == 0; }))
ans = max(ans, processedReqs);
return;
}

// skip requests[i]
dfs(i + 1, processedReqs);

// process requests[i]
--degree[requests[i][0]];
++degree[requests[i][1]];
dfs(i + 1, processedReqs + 1);
--degree[requests[i][1]];
++degree[requests[i][0]];
};

dfs(0, 0);

return ans;
}
};


## JAVA

class Solution {
public int maximumRequests(int n, int[][] requests) {
dfs(0, 0, requests, new int[n]);

return ans;
}

private int ans = 0;

private void dfs(int i, int processedReqs, int[][] requests, int[] degree) {
if (i == requests.length) {
if (Arrays.stream(degree).allMatch(d -> d == 0))
ans = Math.max(ans, processedReqs);
return;
}

// skip requests[i]
dfs(i + 1, processedReqs, requests, degree);

// process requests[i]
--degree[requests[i][0]];
++degree[requests[i][1]];
dfs(i + 1, processedReqs + 1, requests, degree);
--degree[requests[i][1]];
++degree[requests[i][0]];
}
}