Example 3:

Input:
n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]
Output:
 4

Solution

Method 1 – Backtracking with State Validation

Intuition

We want the largest set of requests such that the net change for each building is zero. Since the number of requests is small, we can use backtracking to try all possible subsets and check if the net change is zero for each building.

Approach

For each subset of requests, use backtracking to include or exclude each request.
Track the net change for each building in an array.
If all net changes are zero, update the answer with the size of the subset.
Try all combinations and return the largest valid subset size.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int ans = 0;\n    void dfs(int i, int n, vector<vector<int>>& req, vector<int>& bal, int cnt) {\n        if (i == req.size()) {\n            if (all_of(bal.begin(), bal.end(), [](int x){return x==0;}))\n                ans = max(ans, cnt);\n            return;\n        }\n        dfs(i+1, n, req, bal, cnt);\n        bal[req[i][0]]--;\n        bal[req[i][1]]++;\n        dfs(i+1, n, req, bal, cnt+1);\n        bal[req[i][0]]++;\n        bal[req[i][1]]--;\n    }\n    int maximumRequests(int n, vector<vector<int>>& requests) {\n        vector<int> bal(n);\n        dfs(0, n, requests, bal, 0);\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> ans </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 0</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    void</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> dfs</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> i</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> n</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;-

Related Tags