Problem statement

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

Solution

What is enough here is just to check all 2^m possible options for chose of requests and process each of them in O(n) time with dfs.

Complexity

Time complexity is O(2^n*m). Actually we can keep one more parameter zeroes: number of zeros in our state and process each state in O(1), but in practice it will not give a lot of gain in speed.

Code

class Solution:
    def maximumRequests(self, n, R):
        def dfs(i, state, taken):
            if i == len(R):
                if all(i == 0 for i in state):
                    self.ans = max(self.ans, taken)
                return
            dfs(i + 1, state, taken)
            state[R[i][0]] -= 1
            state[R[i][1]] += 1
            dfs(i + 1, state, taken + 1)
            state[R[i][0]] += 1
            state[R[i][1]] -= 1
        
        self.ans = 0
        dfs(0, [0]*n, 0)
        return self.ans

If we use lru_cache, we can gain speed 2 times, because some problems overlap (but not a lot of them, this is not dp)

class Solution:
    def maximumRequests(self, n, R):
        @lru_cache(None)
        def dfs(i, bal):
            if i == len(R):
                return 0 if all(b == 0 for b in bal) else float('-inf') 
            bal2 = list(bal)
            bal2[R[i][0]] -= 1
            bal2[R[i][1]] += 1
            return max(1 + dfs(i + 1, tuple(bal2)), dfs(i + 1, bal))
        
        return dfs(0, tuple([0] * n))