Skip to content

1601. Maximum Number of Achievable Transfer Requests 👍

  • Time: $O(n \cdot 2^{|\texttt{requests}|})$
  • Space: $O(n + |\texttt{requests}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  int maximumRequests(int n, vector<vector<int>>& requests) {
    int ans = 0;
    vector<int> degrees(n);  // degrees[i] := degrees of the i-th building

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

      // Skip the requests[i].
      dfs(i + 1, processedReqs);

      // Process the requests[i].
      --degrees[requests[i][0]];
      ++degrees[requests[i][1]];
      dfs(i + 1, processedReqs + 1);
      --degrees[requests[i][1]];
      ++degrees[requests[i][0]];
    };

    dfs(0, 0);

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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[] degrees) {
    if (i == requests.length) {
      if (Arrays.stream(degrees).allMatch(d -> d == 0))
        ans = Math.max(ans, processedReqs);
      return;
    }

    // Skip the requests[i].
    dfs(i + 1, processedReqs, requests, degrees);

    // Process the requests[i].
    --degrees[requests[i][0]];
    ++degrees[requests[i][1]];
    dfs(i + 1, processedReqs + 1, requests, degrees);
    --degrees[requests[i][1]];
    ++degrees[requests[i][0]];
  }
}