这道 3548 号题我刷到的时候第一反应是“又一个矩阵题”但仔细读完题面才发现事情没那么简单。等和矩阵分割光“等和”两个字听起来像是二维前缀和的活可题目里藏着另一个更关键的条件分割出来的两个区域都必须连通。这就把问题从“算和”变成了“枚举连通块 验证补集连通”难度直接上了一个台阶。这篇文章我就把这道困难题的完整思路、剪枝细节和调试过程写出来给同样在啃这类题的朋友一个参考。整道题最核心的难点在于你不能只找出一个区域让它和等于总和的一半你还得保证剩下的那一半也是连通的而且两个区域是互补关系你枚举一个区域的时候它的补集是什么形状、连不连通完全是动态变化的。这是典型的“约束搜索”问题暴力枚举所有子集根本不可行必须把搜索空间压缩到“包含某个固定点的连通块”这个范围里。1. 题目定位与问题本质1.1 3548 在力扣题库里是什么难度编号到 3548 的题目基本都是最近几个月新增的周赛压轴题难度定在 Hard 一点也不意外。这类题目通常不是考某个单一知识点而是把“搜索”、“剪枝”、“连通性判断”揉在一起再加上矩阵这个载体很容易把没有经验的人绕晕。从刷题策略的角度讲遇到这种编号非常新的困难题第一件事不是急着看题解而是先自己判断数据范围。矩阵类搜索题的复杂度通常和格子总数 n m * n 强相关如果 n 小于等于 20位掩码枚举是可行的如果 n 到 30 以上就必须靠搜索 剪枝或者深挖题目有没有特殊的数学结构。这道题核心其实就一句话在一个矩阵里找一个连通区域使它的和等于总和的一半同时让补集也连通。 判断连通性是图论问题枚举区域是组合搜索问题两者一结合复杂度就上来了。1.2 问题建模等和、连通、互补三个条件缺一不可先把问题用数学语言拆开。假设矩阵所有格子的和是 total那么一个合法分割要把格子分成两个非空集合 A 和 B满足三个条件A 的所有格子之和等于 total / 2B 的所有格子之和也等于 total / 2其实 A 满足后B 自动满足因为总和固定A 是 4-连通的上下左右相邻B 也是 4-连通的A 和 B 的并集是整个矩阵交集为空。很多人在第一个条件上就翻车忘了判断 total 的奇偶性。如果 total 是奇数直接返回 0因为两个区域的元素和都是整数不可能各分到 half。这一步虽然简单但能省掉后面所有无效搜索。第二个需要注意的点是A 和 B 是互补的不是两个独立选择的区域。所以枚举的时候只需要找其中一个区域另一个区域自动就是补集。这里有个直觉上的陷阱你找了一个连通区域 A 且它的和等于 target很容易想当然认为补集 B 也连通。实际上这个结论完全不成立。举个反例结构在一个 5x5 的矩阵里如果 A 是正中间一列这 5 个格子显然连通但补集是左右两个 2x5 的块它们之间没有任何相邻边所以 B 不连通。 这种情况下即使 A 的和等于 target整个分割也是非法的。1.3 先修知识为什么不能直接套二维前缀和如果题目只要求“找一个矩形区域使它的和等于某个值”那二维前缀和做完二分或者枚举就结束了这是一道中等题。但这里的区域不一定是矩形可以是任意形状的连通块比如一个 L 形、一个 T 形、一条蛇形路径二维前缀和完全处理不了这种非矩形区域。这道题的本质变成了“枚举矩阵中所有包含某个点的连通块”这是一个经典的枚举问题。枚举所有连通块的复杂度理论上是指数级的因为一个连通块可以由很多种形状但在实际数据范围下配合剪枝是能过的。至于补集连通性那就只能老老实实做一次 BFS 或者 DFS 去验证没法取巧。2. 核心算法思路固定起点枚举连通块2.1 固定 (0,0) 所在区域一个映射解决去重我一开始的想法是把所有合法分割都枚举一遍也就是先选 A 再选 B但这样每个合法分割会被正反算两次A 和 B 交换后又是一个重复答案。后来想到一个关键观察任意一个合法分割中左上角格子 (0,0) 一定属于 A 或 B 中的一个。如果它属于 B那我直接把 A 和 B 的名字互换新的 A 就包含了 (0,0)。交换名字之后两个区域的和仍然是 target因为 A 和 B 的和本来都是 target所以这依然是一个合法分割。这就意味着任何一个合法分割都可以唯一地表示成“以 (0,0) 所在的那个区域作为 A”的形式。 因此我只需要枚举所有包含 (0,0) 的连通区域 A检查它的和是否为 target、补集是否连通就能覆盖所有合法分割而且每个分割正好被统计一次。这个映射关系是整道题最重要的剪枝。如果不固定 (0,0)枚举空间直接翻倍而且还得额外处理 A/B 互换的重复。固定起点之后搜索空间直接砍半并且天然避免了重复计数所谓“一个映射解决去重”就是这个意思。2.2 状态设计visited 数组 当前和 外边界在实际写搜索的时候不能真的拿一个 set 去存当前区域的所有格子坐标那样做状态拷贝太慢。我习惯用一个 m*n 的 visited 布尔数组标记哪些格子已经在 A 区域里同时维护一个“外边界”集合 frontier表示当前 A 区域的所有相邻未访问格子。这一步想清楚为什么需要 frontier如果每次扩展都扫描整个矩阵找未访问且与 A 相邻的格子单次扩展代价是 O(m*n)搜索节点一多就爆炸。而维护 frontier 之后每次扩展只需要从 frontier 里选一个格子即可代价降到 O(frontier 大小)。frontier 的更新逻辑是把选中的格子从 frontier 中移除再把该格子周围四个方向上未访问且未在 frontier 中的邻居加进去。这样设计状态还有一个额外好处因为每个新格子都是从 frontier 中加入的所以 A 区域天然是连通的省去了对 A 做连通性验证的开销。这是一个跟朴素的“逐格二选一”枚举完全不同的思路效率差别非常大。2.3 补集连通性检查最容易漏掉的一步A 区域天然连通之后唯一还需要验证的就是补集连通性。每次当当前和 cur 恰好等于 target 时必须停下来对未访问的格子做一次 BFS统计连通分量数量是否为 1。这里的实现细节是找到第一个未访问的格子作为起点BFS 遍历所有未访问格子最后看访问数量是否等于未访问格子总数。有一个常见 bug 是用压缩后的坐标做 BFS比如把二维坐标转成一维编号后直接判断左右相邻结果忘记跨行的情况。比如编号 3 和编号 4 在一维坐标上相邻但如果 n 等于 5编号 3 在第 0 行第 3 列编号 4 在第 0 行第 4 列它们是左右相邻的没问题可是如果 n 等于 2编号 3 是第 1 行第 1 列编号 4 是第 2 行第 0 列它们其实是斜对角不是 4-连通的邻居。所以要么用二维坐标系遍历方向数组要么在做一维编号时通过divmod(pos, n)还原成二维坐标再判断。我推荐直接还原保险且直观。3. 剪枝与实现细节3.1 剩余和剪枝与递归参数设计搜索题的灵魂是剪枝这道题最重要的一条剪枝是“剩余和剪枝”。递归的时候除了维护当前和 cur还要维护一个 rem表示所有未访问格子的总和。如果 cur rem target说明就算把剩下所有格子全部加入 A和也到不了 target必须立即剪枝返回。这里有个容易踩的坑rem 必须是“所有未访问格子”的和而不是“所有未加入 A 的格子”的和。因为补集里的格子虽然不属于 A但它们仍然“未访问”一旦后续扩展路径改变这些格子也可能加入 A。所以递归函数里 rem 应该等于初始 total 减去当前已选区域和 cur即 rem total - cur这样就不需要额外维护了。还有一个更激进的剪枝如果格子值都是非负数那么 cur 只会单调递增一旦 cur 等于 target 就可以直接检查补集并返回不需要继续向深处搜索。因为继续加任何非负格子都会让 cur 超过 target永远不可能再回到 target。这个剪枝要建立在“格子值非负”这个前提上题目如果没有明确说就要谨慎使用。我做到这儿的时候特意看了一眼题目描述格值非负的设定在这道题里是成立的所以可以放心加。3.2 边界扩展法从“选格子”变成“扩边界”这个技巧我觉得是整道题最优雅的地方。朴素的枚举方式是对每个格子做“选/不选”的二叉树递归但这样做会产生大量不连通的集合然后还要验证每个集合是否连通白费大量计算。边界扩展法则相反从 (0,0) 这个种子开始每一步都从当前边界 frontier 里选一个格子加入 A这样产生的每一个中间状态天然就是连通的。但这里又冒出一个新问题同样的连通块可能通过不同的加入顺序被枚举多次。比如一个 2x2 的方块区域可以从左上角开始先加右上角再加左下角也可以先加左下角再加右上角最终都是同一个集合但走了两条不同的递归路径。如果不去重搜索节点会爆炸而且答案会重复计数。我的处理方法是给格子编上唯一 id0 到 m*n-1并且规定每次扩展时只能选择当前 frontier 中 id 最小的那个格子。 这个规则能保证每个连通块只被生成一次。粗略解释一下对于任意一个最终集合 S按照“每次选 frontier 中最小 id”的规则生成选择序列是确定的所以 S 只对应一条递归路径。具体实现时frontier 可以用一个有序结构比如 sorted list或者简单点每次在递归函数里从 frontier 中找最小 id虽然多一点常数但正确性优先。3.3 退化情况一维矩阵、全零矩阵、负数格值调试的时候一定要考虑到矩阵的特殊形态。如果 m 等于 1 或者 n 等于 1问题退化成“一个一维数组切成两个连续区间”此时不需要搜连通块直接前缀和扫一遍找断点复杂度 O(n)。很多搜索代码在二维矩阵上没问题一遇到一维就出各种越界所以我建议直接把这个退化情况单独拎出来处理。全零矩阵则是另一种陷阱。如果所有格子都是 0那么 total 等于 0target 也等于 0任意一个连通区域的和都是 0此时答案可能非常巨大甚至需要取模。如果题目没有特殊说明这种极端情况下搜索会枚举出天文数字个连通块代码直接超时。常见的处理办法是看题目是否对区域面积有约束或者是否要求统计方案数并取模。刷题的时候遇到这种边界值建议先跟题目的样例和范围对照一下确认是否需要特判。还有一种情况是格值可能为负数如果题目允许负值那么 cur 不是单调递增的cur 等于 target 之后继续扩展还可能再次等于 target剪枝逻辑完全不同上一节说的“命中后返回”就不能用了。所以动手写码之前一定要先确认格值约束这是所有剪枝策略的前提。4. 代码实现与复杂度分析4.1 小规模状态压缩兜底方案可运行如果矩阵的格子总数 m*n 不超过 20最稳的做法是位掩码枚举代码简单正确性最容易保证。我把这个版本写出来当作一个可以直接跑的兜底方案。from collections import deque from typing import List class Solution: def waysToPartition(self, grid: List[List[int]]) - int: m, n len(grid), len(grid[0]) N m * n total sum(grid[i][j] for i in range(m) for j in range(n)) if total % 2: return 0 target total // 2 val [grid[i][j] for i in range(m) for j in range(n)] sum_mask [0] * (1 N) for mask in range(1, 1 N): lb mask -mask idx lb.bit_length() - 1 sum_mask[mask] sum_mask[mask ^ lb] val[idx] full (1 N) - 1 def connected(mask: int) - bool: if mask 0: return False start (mask -mask).bit_length() - 1 seen 0 q deque([start]) seen | 1 start while q: pos q.popleft() i, j divmod(pos, n) for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)): ni, nj i di, j dj if 0 ni m and 0 nj n: nxt ni * n nj if (mask nxt) 1 and not ((seen nxt) 1): seen | 1 nxt q.append(nxt) return seen mask ans 0 for mask in range(1, full): if not (mask 1): continue if sum_mask[mask] ! target: continue if connected(mask) and connected(full ^ mask): ans 1 return ans这个版本的核心逻辑就三步预处理所有掩码的和、枚举包含编号 0 格子的掩码、分别验证 A 区和补集的连通性。因为固定了 mask 必须包含编号 0 的格子所以不会把同一分割的正反两版都算进去。复杂度是 O(2^N * N)N 等于 m*n当 N 为 20 的时候大约一千万次操作Python 勉强可以跑如果 N 到 22 就开始吃力了。4.2 基于边界扩展的 DFS 搜索版当格子总数超过位掩码能承受的范围时就要上搜索剪枝了。边界扩展 DFS 的核心代码骨架如下我刻意保留了剪枝和去重逻辑方便参考。from typing import List class Solution: def waysToPartition(self, grid: List[List[int]]) - int: m, n len(grid), len(grid[0]) N m * n total sum(grid[i][j] for i in range(m) for j in range(n)) if total % 2: return 0 target total // 2 val [grid[i][j] for i in range(m) for j in range(n)] visited [False] * N ans 0 dirs ((1, 0), (-1, 0), (0, 1), (0, -1)) def inb(pos): i, j divmod(pos, n) return 0 i m and 0 j n def check_complement(): start -1 for pos in range(N): if not visited[pos]: start pos break if start -1: return False q [start] seen [False] * N seen[start] True cnt 0 while q: pos q.pop() cnt 1 i, j divmod(pos, n) for di, dj in dirs: ni, nj i di, j dj if 0 ni m and 0 nj n: nxt ni * n nj if not visited[nxt] and not seen[nxt]: seen[nxt] True q.append(nxt) return cnt N - sum(visited) def dfs(cur_sum, visited, frontier): nonlocal ans if cur_sum target: return if cur_sum (total - cur_sum) target: return if cur_sum target: if check_complement(): ans 1 return if not frontier: return # 去重规则选 frontier 中 id 最小的格子 nxt_pos min(frontier) frontier.remove(nxt_pos) # 分支1不选 nxt_pos从剩余 frontier 继续 dfs(cur_sum, visited, set(frontier)) # 分支2选 nxt_pos visited[nxt_pos] True new_frontier set(frontier) i, j divmod(nxt_pos, n) for di, dj in dirs: ni, nj i di, j dj if 0 ni m and 0 nj n: cand ni * n nj if not visited[cand]: new_frontier.add(cand) dfs(cur_sum val[nxt_pos], visited, new_frontier) visited[nxt_pos] False visited[0] True frontier set() i0, j0 divmod(0, n) for di, dj in dirs: ni, nj i0 di, j0 dj if 0 ni m and 0 nj n: frontier.add(ni * n nj) dfs(val[0], visited, frontier) return ans这个版本的思路是在每一层递归中从当前边界里挑出编号最小的格子然后分成两个分支要么放弃这个格子要么把它加入 A 区域。放弃之后这个格子以后也不能再选了这正好对应了“边界最小 id”的唯一生成顺序规则。这样每个连通块只被枚举一次避免了重复计数。运行起来之后你会发现搜索树依然很庞大但“剩余和剪枝”配合“命中 target 后立即 return”能够砍掉大量分支。如果题目数据范围较大还可以进一步优化把 frontier 从 set 改成有序结构减少 min 操作的耗时或者把 visited 数组改成整数掩码通过位运算判断邻居状态。不过这些都是常数优化核心思路不变。4.3 复杂度分析与算法选型建议两个版本的适用场景非常清晰。位掩码枚举版本的编写效率高不容易出错适合 m*n 小于等于 20 的矩阵边界扩展 DFS 版本理论上能处理更大的矩阵但复杂度高度依赖数据分布和剪枝效果最坏情况下依然是指数级。实际刷题时选哪种取决于你第一眼看到的约束条件如果 m 和 n 都很小比如都是 3 或 4直接位掩码枚举是最省脑子的如果 mn 达到 25 以上可以尝试搜索 剪枝如果 mn 超过 30那大概率这道题另有数学结论不是纯粹的搜索题需要回到题目重新分析。 我自己的习惯是先用位掩码版本把思路验证一遍确认算法正确再根据数据范围决定要不要改成搜索版。先保证方向对再追求性能。5. 常见问题与调试实录5.1 TLE剪枝不彻底和重复枚举TLE 是刷这类题最常遇到的错误。我自己的搜索版本一开始没有做“固定 (0,0)”的去重结果一个 4x4 的矩阵跑了半天都出不来。原因很简单每个合法分割被正反统计了两次搜索工作量直接翻倍而且那些本来会在中途被剪掉的分支也多走了一遍。排查方法很简单写一个计数器统计递归函数的调用次数然后在本地用 3x3、4x4 的随机小矩阵跑一遍对比剪枝前后的调用次数。如果发现调用次数是预期结果的指数倍优先检查去重逻辑看看是不是最小 id 规则没生效。还有一个常见问题是 frontier 用 set 之后每次递归都拷贝整个 set这个拷贝开销很大。可以尝试用列表加 visited 标记来代替虽然逻辑稍微绕一点但性能提升明显。5.2 WA补集连通性被忽略这个坑我踩过一次之后印象特别深。当时我写完第一次版本用题目给的示例能过就顺手交了一发结果直接 WA。查了半天发现我的代码里只验证了 A 区域的和等于 target完全没验证补集连通性。为什么示例能过因为示例恰好补集是连通的掩盖了问题。调试这类 WA 的最好方式是自己构造一个“A 连通但补集不连通”的矩阵比如让 A 占满中间一列补集分成左右两块然后观察你的代码是否错误地把它当成合法分割输出了。在本地加上一个辅助断言函数对所有输出方案手动检查补集连通性能快速暴露问题。另外检查补集的 BFS 一定要确保被访问的格子数量等于未访问格子总数而不是等于某个固定值否则在边界形状变化时会漏判。5.3 边界值与特殊矩阵的坑特殊矩阵主要看三类总和为奇数、target 为 0、一维退化。总和为奇数的情况最省事开头判断一下直接返回 0但有人会把 total 除以 2 用整除结果 target 判断错误导致整个搜索方向跑偏。我建议直接先做if total % 2: return 0不要靠后面的搜索去碰运气。target 为 0 的情况比如全零矩阵比较棘手。如果题目保证格值非负那么cur target之后必须停止扩展否则 cur 会变成正数永远回不到 0。但如果格值里面有负数这个剪枝就错了。我在调试时遇到过一个情况一个看起来非常小的矩阵因为没处理 target 为 0 的爆炸式枚举直接卡死。最后在本地把矩阵打印出来逐一检查才意识到问题出在“命中 target 后继续扩展”这条路径上。5.4 调试技巧先用 2x2 和 3x3 验证我调试这道题时用的最快方法是构造几个手工小矩阵把答案手算出来再跟代码输出对比。比如一个 2x2 的全 1 矩阵总和是 4target 是 2包含左上角格子且和为 2 的连通块有两个分别是横向的两个格子和纵向的两个格子所以答案应该是 2。再比如 3x3 全 1 矩阵总和 9 是奇数答案应该是 0。这两个用例能快速验证最基础的逻辑。如果想进一步验证连通性和补集检查可以用我之前构造过的矩阵grid [ [1, 2, 1], [2, 2, 2], [1, 2, 1] ]总和是 14target 是 7。左上角 2x2 方块的和是 1 2 2 2 7补集是右边一列加下面一行具体为 1 2 2 1 1 7而且补集是一条连通的折线。这个用例能验证“A 连通 补集连通”的真正合法分割。如果代码在这个用例上输出正确再换那个“中间一列 A、左右两半 B”的反例结构测一次很快就能定位问题。6. 个人体会与刷题扩展6.1 这类题的通法套路刷多了矩阵分割类题目之后我总结出一个套路先找总和和奇偶性再固定一个必选点去重然后用边界扩展法枚举连通块最后验证补集条件。这个套路不仅适用于这一道题很多类似问题都能套进去。比如“把一个图分成两个连通分量且满足某种权重约束”的题核心思路其实一样只是把矩阵换成了图。很多人在搜索题里栽跟头不是因为想不出 DFS而是因为枚举状态太大、没有合适的剪枝。固定起点这一步是全局性的剪枝能把搜索空间砍掉指数级的分支。边界扩展法则是从结构上避免了无效状态。这两招结合在一起搜索题的骨架就立起来了。6.2 从 I 到 II判定题变成计数题之后如果这个系列的第一版只是判断是否存在合法分割那找到一个答案就可以提前退出到了 II 要求计数就必须遍历整个搜索树所有能提前退出的剪枝都不能用了去重的正确性也变得更加重要。这也是为什么我特别强调“固定 (0,0)”这个映射在判定版里重复枚举可能只是浪费时间在计数版里重复枚举会让答案直接翻倍属于致命错误。从做题策略上讲遇到系列题的第二版一定要先跟第一版对比看新增的约束是什么。是输出方案总数是要求最小面积还是两个区域交换算不算同一种这些细节直接决定搜完整个树还是可以提前剪枝。每多一个限制状态设计和剪枝逻辑都可能需要调整。6.3 最后分享一个调试小技巧我调试这种带连通性检查的搜索题时会在本地开一个 debug 模式把每次递归命中的合法分割以字符画的形式打印出来A 区域用 # 标记B 区域用 . 标记然后肉眼检查。字符画能一眼看出补集到底连不连通比在脑内模拟快得多。# # . # # . . . .像上面这样A 是左上角的 2x2 方块补集是右边一列加下面一行是连通的所以这是一个合法分割的候选。但如果打印出来是# . . # . . # . .A 是中间一列补集左右分离哪怕 A 的和等于 target也是非法方案。这种可视化检查在调试 WA 时非常高效强烈建议遇到类似问题的时候用上。这道题本身虽然难但把“固定起点 边界扩展 补集验证”这套组合拳打熟之后以后再遇到矩阵分割、连通区域枚举类的题目都会觉得坦荡很多。