剪枝

副标题 / 摘要 组合总和是回溯专题里第一道真正把“组合模板 + 目标约束 + 剪枝”揉在一起的题。你要学会的不只是枚举，而是怎样用排序和剩余值 remain 把搜索树收紧。 预计阅读时长：12~15 分钟 标签：Hot100、回溯、组合、剪枝 SEO 关键词：Combination Sum, 组合总和, 回溯, 剪枝, DFS 元描述：通过 LeetCode 39 建立组合型回溯加剪枝模板，理解可重复选取、排序与 remain 约束。 目标读者 已经做过 78. 子集，准备把回溯模板升级到“带约束搜索”的学习者 想搞清楚“同一个数可以重复使用”时递归边界怎么写的开发者 需要做资源打包、预算组合、规格拼装类组合搜索的工程师 背景 / 动机 这题是很多人真正开始理解“回溯不是暴力乱搜”的分水岭。 因为它同时有三件事： 仍然是组合问题，所以要保持顺序无关 候选数字可以重复使用 目标和 target 给了你天然剪枝条件 如果你只会硬搜，代码虽然也许能过，但模板不稳定。 而一旦你把“排序 + remain + 从 i 开始递归”的逻辑想清楚，这一类题都会顺很多。 核心概念 path：当前正在尝试的一组组合 remain：当前还差多少才能凑到目标值 从 i 继续递归：表示当前数字可以重复使用 排序剪枝：若 candidates[i] > remain，后面的数更大，可直接停止 A — Algorithm（题目与算法） 题目还原 给定一个无重复元素的整数数组 candidates 和一个目标值 target， 找出所有和为 target 的不同组合。 ...

副标题 / 摘要 子图匹配是图查询里的硬骨头：理论上 NP-hard，但工程里并不是“只能慢”。本文按 ACERS 模板讲清 VF2 / Ullmann 的核心思路，并把重点放在真正决定性能的地方：候选生成与剪枝策略。 预计阅读时长：15~20 分钟 标签：子图匹配、VF2、Ullmann、图数据库 SEO 关键词：Subgraph Isomorphism, VF2, Ullmann, candidate pruning, 图模式匹配 元描述：从 NP-hard 的子图同构问题出发，解释 VF2/Ullmann 机制与工程剪枝实践，覆盖图数据库常见受限模式查询。 目标读者 需要在图数据库做模式查询、规则检测、风险关系识别的工程师 已掌握 BFS/DFS/连通分量，希望进阶图匹配能力的开发者 需要在“可解释规则匹配”与“性能约束”之间做权衡的算法同学 背景 / 动机 你在图数据库里会经常遇到这种需求： 找出“一个人-两家公司-同一设备”的可疑结构 找出“作者-论文-机构”的特定模式 找出“交易链中的环形洗钱模板” 这类查询本质是 Subgraph Isomorphism（子图同构）： 给模式图 Q，在数据图 G 中找结构与约束都满足的嵌入映射。 理论上它是 NP-hard，意味着最坏情况很难避免指数爆炸。 但工程上大多数查询是受限模式（有标签、有方向、有属性、有小模式规模），因此性能核心变成： 先把候选压到很小，再做匹配搜索。 核心概念 Subgraph Isomorphism：模式图节点到数据图节点的单射映射，保边关系成立 受限模式（constrained pattern）：标签、方向、度数、属性谓词限制 候选集（candidate set）：每个模式节点可能映射到的数据节点集合 剪枝（pruning）：在搜索树早期排除不可能映射，减少回溯分支 VF2：基于状态扩展与可行性检查的深度优先匹配框架 Ullmann：基于候选矩阵与邻域一致性迭代收缩的经典方法 A — Algorithm（题目与算法） 题目还原（工程化） 给定： 数据图 G=(V_G,E_G)（通常很大） 模式图 Q=(V_Q,E_Q)（通常较小） 节点/边约束（标签、方向、属性谓词） 目标： ...

副标题 / 摘要 这题的关键不是二分，而是利用“行列都单调”的结构，从**右上角（或左下角）**像走楼梯一样移动：每一步都能排除一整行或一整列，从而把复杂度降到 O(m+n)。 预计阅读时长：10~13 分钟 标签：Hot100、矩阵、单调性、指针 SEO 关键词：搜索二维矩阵 II, 单调矩阵查找, 右上角搜索, O(m+n), LeetCode 240 元描述：在行列均升序的矩阵中搜索 target：从右上角阶梯式移动，每步排除一行或一列，O(m+n)/O(1) 解法与多语言实现。 目标读者 刷 Hot100，希望掌握“二维单调结构剪枝”模板的学习者 写过二分但总在二维问题里迷路的中级开发者 在工程中需要查询/裁剪/定位二维单调表格的工程师 背景 / 动机 二维表在工程里很常见：费率表、校准表、阈值表、网格配置表等。 当一个表满足“横向递增 + 纵向递增”的 二维单调（monotone matrix） 特性时，很多查询不需要 O(mn) 全扫。 这题就是经典入门：用单调性做剪枝，把搜索降成线性级别。 核心概念 概念 含义 在本题的作用 二维单调矩阵 行升序、列升序 保证“比较一次就能排除一行/列” 右上角起点 右上角元素：左边更小、下边更大 决策方向天然明确 剪枝 排除不可能包含 target 的行/列 每步减少搜索空间 O(1) 额外空间 只用 i/j 指针 适合大矩阵与性能场景 A — Algorithm（题目与算法） 题目还原 给定一个 m x n 矩阵 matrix 和一个目标值 target。矩阵满足： ...