https://leetcode.com/problems/maximum-number-of-achievable-transfer-requests/ from Amazon

The contrains say requests.length will be less than 16. So, in the context, I didn’t know if there’s any greedy approach for this, but it seems to me that I can solve this in a brute force way since I only need to check all the combination of edges (2^16), and for each combination, I just need O(n) time to figure out if it’s valid or not. So, the total time will be 20*2^16, which is okay in terms of time complexity.

So, to go through all the combination, below is a very classic way. I loop through from 0 to (1«16) and then use the bit of each position to represent our choice for each edge. Once we know what edges we pick, we just need to compute the number of employee in each building, and make sure if it’s valid or not (net change is zero for all buildings).

 1class Solution {
 2public:
 3    int maximumRequests(int n, vector<vector<int>>& requests) {
 4        int N = requests.size();
 5        int best = 0;
 6        for (int i=0; i<(1<<N); i++) {
 7            int cnt = 0;
 8            vector<int> nums(n);
 9            for (int j=0; j<N; j++) {
10                if (i & (1<<j)) {
11                    cnt++;
12                    nums[requests[j][0]]--;
13                    nums[requests[j][1]]++;
14                }
15            }
16            bool work = true;
17            for (int j=0; j<n; j++) {
18                if (nums[j]) work = false;
19            }
20            if (work and cnt > best) best = cnt;
21        }
22        return best;
23    }
24};