LeetCode 1601：可行转移请求数求解疑问及代码问题分析

一、你的代码错误原因分析 #

你的代码思路是统计每个建筑的出请求数（out）和入请求数（in），然后把每个建筑的min(out[i], in[i])相加作为答案。这种贪心思路存在本质问题：它只单独考虑每个建筑的出入请求数量，忽略了请求之间的关联性。

举个反例：假设n=2，requests=[[0,1],[0,1],[1,0]]，你的代码计算min(2,1) + min(1,2) = 1+1=2，这个结果看似正确；但如果是n=3，requests=[[0,1],[0,1],[1,2],[2,0]]，你的代码计算min(2,1) + min(2,1) + min(1,1) =1+1+1=3，但实际上不存在任何3个请求的子集满足所有建筑净变化为0——所有3个请求的组合都会导致至少一个建筑的净变化不为0，此时你的答案就完全错误了。

核心问题在于：单个建筑的min(out[i], in[i])对应的请求，无法保证能和其他建筑的请求组合后，让所有建筑的净变化同时为0。贪心策略在这里无法覆盖全局约束。

二、示例输入n=3, requests=[[2,2],[2,1],[1,0]]的预期输出解析 #

首先明确规则：只有当所有建筑的员工净变化为0时，所选请求子集才是可行的。我们逐一分析可能的请求组合：

• 选[2,2]：这个请求是员工从建筑2转移到自身，相当于没有人员流动，所有建筑的净变化都是0，因此这个子集可行，数量为1。
• 选[2,1]：建筑2净变化-1，建筑1净变化+1，其他建筑净变化0，不满足所有建筑净变化为0的要求，不可行。
• 选[1,0]：建筑1净变化-1，建筑0净变化+1，其他建筑净变化0，同样不满足要求，不可行。
• 选任意两个或三个请求：都会导致至少一个建筑的净变化不为0（比如选[2,1]+[1,0]，建筑2净变化-1，建筑0净变化+1），均不可行。

因此最大可行请求数是1。你之前的误解是以为单独选[1,0]可行，但实际上建筑0的净变化是+1（只有入没有出），不符合“净变化为0”的要求，所以这个请求不能单独算作可行子集。

三、为什么需要回溯解法 #

这个问题的本质是从请求列表中选出最大的子集，使得每个建筑的净人员变化为0。每个请求有“选”或“不选”两种状态，我们需要枚举所有可能的子集，检查是否满足全局约束，并记录最大的可行子集大小。

由于题目限制请求数量最多为16，枚举所有子集的时间复杂度是O(2^16)=65536，完全在可接受范围内。回溯法是实现这种枚举的常用方式：通过递归遍历每个请求，实时维护每个建筑的净变化值，当处理完所有请求后，若所有建筑的净变化都为0，则更新最大可行请求数。

贪心策略之所以失效，是因为它无法处理请求之间的全局关联性——单个建筑的最优选择，无法保证全局所有建筑都满足约束。而回溯（或位掩码枚举）可以完整遍历所有可能的组合，确保找到真正的最大值。

内容的提问来源于stack exchange，提问作者nanosoft