目标和问题的存在性判断是我在刷题和面试里见过最容易被低估的一道题。表面上看它比 LeetCode 494 原题求方案数少了一个“统计”步骤好像只要把 DFS 改成提前返回 true 就行但实际上一旦你把“能不能凑出来”当成核心问题解法会完全换一套思路——从回溯剪枝到动态规划布尔转移再到 bitset 位移和 Meet in the Middle每一步都是对“存在性”这个特性的深度利用。这篇文章我用实际跑过的代码和踩过的坑把这几种解法从头到尾拆一遍适合刚接触动态规划的初学者也适合准备算法面试想快速把这类题串起来的人。1. 先搞清楚题目在问什么存在性不是计数1.1 题目描述与两种问法目标和问题Target Sum的原题描述是给定一个非负整数数组 nums 和一个目标整数 target你可以在每个数字前面添加 “” 或 “-” 号然后计算这个表达式的值。LeetCode 494 问的是“一共有多少种不同的表达式计算结果等于 target”而“存在性”版本只问“是否存在至少一种正负号组合使结果等于 target”返回值是布尔值 true 或 false。举个例子nums [1, 1, 1, 1, 1]target 3。计数版本答案是 5 种存在性版本直接返回 true因为你有 “-11111 3” 这种组合。两者对信息的要求差别很大计数版本必须完整遍历所有状态而存在性版本只要找到一个就结束这个特性是所有剪枝和位运算优化的基础。1.2 为什么单独把“存在性”拿出来研究很多人在刷题时习惯直接套模板看到这个题就上 DFS然后统计答案最后“顺手”改成 return true。但实际面试里我遇到过好几次面试官刻意把问题改成“只判断存不存在”目的就是看你能不能抓住“提前终止”和“布尔状态压缩”这两个点。从数据结构设计角度看“存在性”对应的是集合的成员关系用布尔数组就可以表达而“计数”对应的是整数累加必须用 int 数组。这个差异会直接影响 DP 的空间复杂度和转移方式。再往深一层说存在性问题往往可以转化为“子集和问题”Subset Sum而子集和是背包问题的基础变体搞懂了它后续的“分割等和子集”“能否装满背包”这些问题都能顺带解决。2. 第一直觉DFS / 回溯能不能解决问题2.1 回溯的递归设计与终止条件最直观的思路是枚举每个数字的正负号生成一棵深度为 n 的二叉树。每个节点有两种选择加正号和加负号。递归函数可以写成bool dfs(vectorint nums, int i, int curSum, int target) { if (i nums.size()) { return curSum target; } // 尝试加号 if (dfs(nums, i 1, curSum nums[i], target)) return true; // 尝试减号 if (dfs(nums, i 1, curSum - nums[i], target)) return true; return false; }这段代码本身没有逻辑错误但它暴露了一个关键问题没有任何剪枝的情况下最坏复杂度是 O(2^n)n 稍微超过 20 就没法看。我在实际写这道题时第一版直接这么交n25 就开始卡顿n30 基本等于死循环。所以回溯能做但必须搭配剪枝否则只适合作为理论上的 baseline。2.2 剪枝技巧排序 剩余范围判断想让回溯跑得快一个非常有效的剪枝思路是先算当前下标 i 之后所有元素能贡献的最大值和最小值看目标 curSum 是否在可达范围内。为了获得更紧的范围可以先把数组按绝对值从大到小排序然后预处理后缀和。bool dfs(vectorint nums, int i, int curSum, int target, vectorint suffix) { if (i nums.size()) { return curSum target; } // 如果当前和加上后面全部为正都够不到 target剪掉 if (curSum suffix[i] target) return false; // 如果当前和减去后面全部为负也超过 target剪掉 if (curSum - suffix[i] target) return false; if (dfs(nums, i 1, curSum nums[i], target, suffix)) return true; if (dfs(nums, i 1, curSum - nums[i], target, suffix)) return true; return false; }实际测试中加了后缀范围剪枝之后大部分随机数据都能在极短时间内返回因为一旦有一条路径命中 target整个搜索就停住了。这就是存在性题目最大的优势不需要遍历整棵搜索树。不过要提醒一句剪枝只能应对 n 在 20~30 左右的场景n 到 40 以上仍然吃紧这时候就该切换到 DP 或 Meet in the Middle。2.3 回溯的适用边界我个人的判断标准很简单n 20 直接回溯没任何问题n 30 可以加后缀剪枝赌一把但前提是数据比较“散”能剪掉大量分支n 超过 30 就不要再想搜索了老老实实上动态规划。另外还要注意数组里有大量 0 时回溯会产生很多重复分支因为 0 加正号和减号结果一样这时候最好在递归里跳过值为 0 的元素或者换个解法。3. 核心技巧把 ± 号问题转化为子集和问题3.1 数学推导如果只会 DFS这道题只能算“做过”谈不上“吃透”。真正让目标和问题变得通用的是下面这个数学变形。假设最终表达式里加正号的数字之和为 P加负号的数字绝对值之和为 Q原始数组所有元素之和为 sum。那么有两个恒等式P Q sum P - Q target两个式子相加得到 2P sum target所以P (sum target) / 2这个推导意味着原问题等价于“从 nums 中选出若干个数使它们的和恰好等于 P”。一旦想明白这一步“目标和问题”就直接变成了“子集和问题”Subset Sum。这是我当时觉得最惊艳的地方因为子集和是背包问题里更基础的形态有一整套成熟解法可以迁移。3.2 前置条件判断转化之后别急着写 DP先做两个硬校验否则数组越界或者逻辑错误会一个接一个。第一(sum target) 必须是偶数否则 P 是小数根本不存在第二target 的绝对值不能大于 sum否则所有数字同号也凑不出来直接返回 false。这两个条件都能在 O(1) 时间里排除大量无效输入放在代码最前面可以避免后续很多无谓计算。int total accumulate(nums.begin(), nums.end(), 0); if (abs(target) total || (total target) % 2 ! 0) { return false; } int subsetTarget (total target) / 2;这里有个容易踩的细节target 可能是负数所以取绝对值判断但 subsetTarget 一定是非负的因为 total target 0 已经被第一个条件保证了。4. 动态规划实现与滚动数组优化4.1 二维 DP 的正确写法子集和问题的布尔 DP 是很经典的模板。定义 dp[i][j] 表示“处理完前 i 个元素时是否存在一种选法使和为 j”。状态转移只考虑当前元素拿或不拿dp[i][j] dp[i-1][j] || dp[i-1][j - nums[i-1]]初始条件是 dp[0][0] true表示一个元素都不选时和为 0 这件事一定成立。二维写法的好处是直观适合在讲解时展示状态含义vectorvectorbool dp(n 1, vectorbool(subsetTarget 1, false)); dp[0][0] true; for (int i 1; i n; i) { for (int j 0; j subsetTarget; j) { dp[i][j] dp[i-1][j]; if (j nums[i-1]) { dp[i][j] dp[i][j] || dp[i-1][j - nums[i-1]]; } } } return dp[n][subsetTarget];这段代码的时间复杂度是 O(n * subsetTarget)空间复杂度 O(n * subsetTarget)。当 nums.size() 比较小但 sum 很大时比如 n200、sum100000时间上可以接受但二维 bool 数组占 200 * 100001 个字节也就是约 20MB勉强还行如果 input 更极端就必须做空间优化。4.2 一维滚动数组与倒序更新的原因仔细观察转移方程第 i 行的状态只依赖第 i-1 行所以完全可以用一维数组滚动更新。核心代码如下vectorbool dp(subsetTarget 1, false); dp[0] true; for (int num : nums) { for (int j subsetTarget; j num; --j) { dp[j] dp[j] || dp[j - num]; } } return dp[subsetTarget];这里有一段我在学习时很长时间没想明白的细节为什么内层循环必须从大到小我最初写成从 num 到 subsetTarget 的正序遍历然后发现结果变成了“每个元素可以被选多次”也就是完全背包的效果。原因在于正序遍历时dp[j - num] 可能已经在当前本轮循环中被更新过等价于把同一个 num 用了两次而倒序遍历时j - num 小于 j在本轮循环里还没被更新拿到的仍然是上一轮的状态。这正好保证了“每个元素只用一次”符合 0/1 背包的语义。提示如果你以后做“数字可以重复使用”的题目比如硬币无限量的组合问题就反过来用正序遍历。判断用正序还是倒序本质是判断元素是否允许复用这个规律适用于所有背包类 DP。实测下来一维滚动数组之后空间降为 O(subsetTarget)代码也精简不少。对于存在性问题bool 数组的好处是内存紧凑cache 友好度比 int 高实际运行速度比计数版本的同规模 DP 快不少。4.3 bitset 优化把 DP 变成位运算如果 subsetTarget 比较大但还在可接受范围内有一个更狠的优化用 bitset 代替 bool 数组。核心思想是把 dp 数组看成一个二进制位集合第 i 位为 1 表示“和为 i 是可达的”。每个数字 num 的作用就是把这个集合向左移动 num 位再与原集合取或bitset100001 dp; dp[0] 1; for (int num : nums) { dp | (dp num); } return dp[subsetTarget];这个写法非常简洁而且因为 CPU 位运算天然支持 64 位甚至更宽的并行操作实际运行速度比一维 bool 数组还要快几倍。我拿 n200、sum20000 的数据对比过bool 数组 DP 大约需要几十毫秒bitset 几乎瞬时完成。bitset 的代价是需要在编译期确定最大长度。如果题目不能提前预知上限可以用变长 bitset 的库或者直接用 Python 的 int 类型模拟位集——Python 的 int 本身是无限长的左移和或运算性能也不错。但如果在 C 面试里提到 bitset一定要说清楚这个固定长度的限制否则面试官会认为你只记住了代码没理解原理。4.4 复杂度对比解法时间复杂度空间复杂度适用规模DFS 剪枝最坏 O(2^n)O(n)n 25~30二维 DPO(n * P)O(n * P)n 较小且 P 可控一维 DPO(n * P)O(P)大多数常规题目bitsetO(n * P / word_size)O(P)P 已知且可开数组这里 P (sum target) / 2。选择顺序我的经验是先做数学转化再做前置条件判断如果 P 不大小于十万量级一维 DP 足够如果 P 很大但 n 很小比如 n 25考虑回溯如果 n 在 30~40 之间且 P 非常大DP 和回溯都悬那么下一个方案才是正解。5. 数组规模变大Meet in the Middle 方案5.1 什么时候该考虑 Meet in the Middle动态规划虽然好用但它的复杂度受限于 subsetTarget 的大小。当数组元素很大、目标也很大时比如 n40、每个数最大 10^9sum 能达到 4 * 10^10这时候别说开数组连遍历一遍 P 都不可能。而回溯的 2^40 次方也约等于 1 万亿同样不可行。Meet in the Middle下文简称 MITM的思路是把数组分成两半分别枚举每一半的所有子集和然后再把两半的结果合并起来检查。枚举半段数组的所有子集复杂度是 2^(n/2)n40 时是 2^20 104 万完全可行。这个方案的适应场景非常清晰n 在 20~40 之间且 sum 很大DP 空间吃不下的时候。5.2 分半枚举 哈希匹配实现具体做法分三步。第一步把原数组对半切开第二步用位运算枚举每一半所有子集和存到两个 vector 里第三步遍历左半的每个和 left在右半集合里查找是否存在 right subsetTarget - left。vectorlong long getSubsetSums(vectorint nums, int l, int r) { vectorlong long res; int len r - l; for (int mask 0; mask (1 len); mask) { long long sum 0; for (int i 0; i len; i) { if (mask (1 i)) sum nums[l i]; } res.push_back(sum); } return res; } bool canPartition(vectorint nums, int target) { int n nums.size(); int mid n / 2; vectorlong long left getSubsetSums(nums, 0, mid); vectorlong long right getSubsetSums(nums, mid, n); sort(right.begin(), right.end()); for (long long v : left) { long long need target - v; if (binary_search(right.begin(), right.end(), need)) { return true; } } return false; }对右半排序再二分查找整体复杂度是 O(2^(n/2) * log(2^(n/2)))空间复杂度 O(2^(n/2))。我在本地测试 n40 时左右各 2^20 个子集和排序加二分查找大约几百毫秒比任何 DP 和回溯都快得多而且完全不受数值范围限制。5.3 三种核心方案怎么选我按实际解决问题的顺序排一下优先级先做数学转化和前置判断如果转换后的子集和目标 P 不大比如 10^6直接用 bitset 或一维 DP如果 P 极大但 n 30优先试试剪枝回溯如果 n 在 30~40 之间直接上 MITM超过 40 且 P 极大那通常只能靠贪心或近似算法但这类题在纯算法面试里基本不会出现。这里还要说一个细节MITM 在“计数版目标和问题”里也适用只不过合并时需要统计右半集合中某个值出现的次数可以用 unordered_map 代替排序二分。我在准备一场对性能要求很高的比赛时用过这个技巧效果比直接 DP 好很多。6. 常见问题与避坑实录6.1 “明明有解但返回 false”的四个坑第一个坑忘记判断 (sum target) 是否为偶数。我最初用 DP 跑案例时遇到 nums [1, 1, 1]target 2。sum 3(sum target) 5无法被 2 整除理论上应该返回 false但如果不提前校验subsetTarget 会被算成 2DP 可能错误地返回 true 或出现越界逻辑。这类问题在单元测试里很容易被漏掉因为大部分测试数据都是设计好的偶数情况。第二个坑一维 DP 的遍历顺序写反。前面反复强调过正序遍历会让每个元素被复用多次导致“明明不加这个数就能凑出来结果加了两次反而也能凑出来”之类的虚真结果。排查方法很简单如果 n 很小把所有部分和打出来看很容易发现重复使用了某个元素。第三个坑目标值超出了所有元素之和。这个其实在前置条件判断里已经处理了但如果你改造成别的变体比如数组里有负数判断条件就要改成 abs(target) 与 abs(sum) 的关系千万别照搬。第四个坑数组里有 0 时回溯递归栈爆炸。0 加正号和负号结果一样但 DFS 会把它当成两个分支递归下去相当于白白翻倍搜索空间。处理方式是在递归前把 0 单独统计只递归非零元素最后判断 0 的个数对结果有没有影响——事实上 0 对 sum 不影响所以结果直接由非零部分决定。6.2 值得提前准备的边界测试用例测试用例期望结果说明nums [], target 0true空集和为 0nums [0], target 0true0 可选可不选都为 0nums [0, 0, 0], target 0true多个 0 不影响nums [1], target 2falsetarget 超过 sumnums [1, 1, 1], target 2false无法整除直接排除nums [3, 5, 8], target 16false所有组合都凑不出 16这些用例里最容易出问题的是 nums [0, 0, 0], target 0。如果用的是“选或不选”模型0 也有选和不选两种选择最终一定存在某种选法使和为 0所以答案是 true。但有些实现把所有 0 忽略后直接返回 dp[subsetTarget]这时候 subsetTarget 0dp[0] 本来就是 true所以结果也是 true不会出错。真正危险的是回溯实现0 会产生大量重复分支但最终能返回只是慢如果还加了“跳过 0”的剪枝反而要注意别把问题跳没了。6.3 面试官常见的追问与变体我归纳了四个高频追问面试前自己过一遍会很有底。第一个如果数字可以重复使用怎么改这相当于把 0/1 背包改成完全背包核心变化就是一维 DP 内层遍历改成正序其它逻辑完全相同。第二个如果要输出一种具体的组合方案怎么做在 DP 记录布尔可达状态的同时额外维护一个 parent 数组标记转移到当前位置的前一个位置最后从 target 反推回去。注意选择“不选”和“选”两条路径都要记录否则反推会乱。第三个如果数组允许负数呢原问题转化公式中 sum 的含义变成正数绝对值之和target 变成绝对值偏移量推导仍然成立但要额外处理数组偏移。这个问题比较刁钻我面试时被问过一次当场推公式推了很久。第四个如果题目改成“能否把数组分成两个和相等的子集”怎么做这就是经典的 Partition Equal Subset Sum本质上等价于子集和问题取 target sum / 2先判断 sum 是否为偶数然后跑 DP 即可。会了目标和问题这道题基本是送分题。7. 我的一点个人体会把这几种解法都写熟之后我最大的感受是存在性问题虽然看起来只是“计数问题去掉计数”但它的价值在于逼你重新思考信息量的边界。计数版本必须遍历所有可能性而存在性版本允许你随时停手这种“提前终止”思维在工程里也很常见——比如缓存系统判断 key 是否存在、图算法判断两个节点是否连通都是同一个逻辑内核。我自己在刷题和面试时形成的习惯是拿到题目先问一句“到底是判断存在还是统计数量”这句话能决定整个解法的方向。如果只是判断存在优先考虑布尔 DP 和位运算因为它们不仅快而且代码极短只有 n 特别大且值域特别散时才考虑 MITM。希望这篇拆解能帮你在下一次遇到这类题目时少走几个我当年走过的弯路。
目标和问题的存在性判断是我在刷题和面试里见过最容易被低估的一道题。表面上看它比 LeetCode 494 原题求方案数少了一个“统计”步骤好像只要把 DFS 改成提前返回 true 就行但实际上一旦你把“能不能凑出来”当成核心问题解法会完全换一套思路——从回溯剪枝到动态规划布尔转移再到 bitset 位移和 Meet in the Middle每一步都是对“存在性”这个特性的深度利用。这篇文章我用实际跑过的代码和踩过的坑把这几种解法从头到尾拆一遍适合刚接触动态规划的初学者也适合准备算法面试想快速把这类题串起来的人。1. 先搞清楚题目在问什么存在性不是计数1.1 题目描述与两种问法目标和问题Target Sum的原题描述是给定一个非负整数数组 nums 和一个目标整数 target你可以在每个数字前面添加 “” 或 “-” 号然后计算这个表达式的值。LeetCode 494 问的是“一共有多少种不同的表达式计算结果等于 target”而“存在性”版本只问“是否存在至少一种正负号组合使结果等于 target”返回值是布尔值 true 或 false。举个例子nums [1, 1, 1, 1, 1]target 3。计数版本答案是 5 种存在性版本直接返回 true因为你有 “-11111 3” 这种组合。两者对信息的要求差别很大计数版本必须完整遍历所有状态而存在性版本只要找到一个就结束这个特性是所有剪枝和位运算优化的基础。1.2 为什么单独把“存在性”拿出来研究很多人在刷题时习惯直接套模板看到这个题就上 DFS然后统计答案最后“顺手”改成 return true。但实际面试里我遇到过好几次面试官刻意把问题改成“只判断存不存在”目的就是看你能不能抓住“提前终止”和“布尔状态压缩”这两个点。从数据结构设计角度看“存在性”对应的是集合的成员关系用布尔数组就可以表达而“计数”对应的是整数累加必须用 int 数组。这个差异会直接影响 DP 的空间复杂度和转移方式。再往深一层说存在性问题往往可以转化为“子集和问题”Subset Sum而子集和是背包问题的基础变体搞懂了它后续的“分割等和子集”“能否装满背包”这些问题都能顺带解决。2. 第一直觉DFS / 回溯能不能解决问题2.1 回溯的递归设计与终止条件最直观的思路是枚举每个数字的正负号生成一棵深度为 n 的二叉树。每个节点有两种选择加正号和加负号。递归函数可以写成bool dfs(vectorint nums, int i, int curSum, int target) { if (i nums.size()) { return curSum target; } // 尝试加号 if (dfs(nums, i 1, curSum nums[i], target)) return true; // 尝试减号 if (dfs(nums, i 1, curSum - nums[i], target)) return true; return false; }这段代码本身没有逻辑错误但它暴露了一个关键问题没有任何剪枝的情况下最坏复杂度是 O(2^n)n 稍微超过 20 就没法看。我在实际写这道题时第一版直接这么交n25 就开始卡顿n30 基本等于死循环。所以回溯能做但必须搭配剪枝否则只适合作为理论上的 baseline。2.2 剪枝技巧排序 剩余范围判断想让回溯跑得快一个非常有效的剪枝思路是先算当前下标 i 之后所有元素能贡献的最大值和最小值看目标 curSum 是否在可达范围内。为了获得更紧的范围可以先把数组按绝对值从大到小排序然后预处理后缀和。bool dfs(vectorint nums, int i, int curSum, int target, vectorint suffix) { if (i nums.size()) { return curSum target; } // 如果当前和加上后面全部为正都够不到 target剪掉 if (curSum suffix[i] target) return false; // 如果当前和减去后面全部为负也超过 target剪掉 if (curSum - suffix[i] target) return false; if (dfs(nums, i 1, curSum nums[i], target, suffix)) return true; if (dfs(nums, i 1, curSum - nums[i], target, suffix)) return true; return false; }实际测试中加了后缀范围剪枝之后大部分随机数据都能在极短时间内返回因为一旦有一条路径命中 target整个搜索就停住了。这就是存在性题目最大的优势不需要遍历整棵搜索树。不过要提醒一句剪枝只能应对 n 在 20~30 左右的场景n 到 40 以上仍然吃紧这时候就该切换到 DP 或 Meet in the Middle。2.3 回溯的适用边界我个人的判断标准很简单n 20 直接回溯没任何问题n 30 可以加后缀剪枝赌一把但前提是数据比较“散”能剪掉大量分支n 超过 30 就不要再想搜索了老老实实上动态规划。另外还要注意数组里有大量 0 时回溯会产生很多重复分支因为 0 加正号和减号结果一样这时候最好在递归里跳过值为 0 的元素或者换个解法。3. 核心技巧把 ± 号问题转化为子集和问题3.1 数学推导如果只会 DFS这道题只能算“做过”谈不上“吃透”。真正让目标和问题变得通用的是下面这个数学变形。假设最终表达式里加正号的数字之和为 P加负号的数字绝对值之和为 Q原始数组所有元素之和为 sum。那么有两个恒等式P Q sum P - Q target两个式子相加得到 2P sum target所以P (sum target) / 2这个推导意味着原问题等价于“从 nums 中选出若干个数使它们的和恰好等于 P”。一旦想明白这一步“目标和问题”就直接变成了“子集和问题”Subset Sum。这是我当时觉得最惊艳的地方因为子集和是背包问题里更基础的形态有一整套成熟解法可以迁移。3.2 前置条件判断转化之后别急着写 DP先做两个硬校验否则数组越界或者逻辑错误会一个接一个。第一(sum target) 必须是偶数否则 P 是小数根本不存在第二target 的绝对值不能大于 sum否则所有数字同号也凑不出来直接返回 false。这两个条件都能在 O(1) 时间里排除大量无效输入放在代码最前面可以避免后续很多无谓计算。int total accumulate(nums.begin(), nums.end(), 0); if (abs(target) total || (total target) % 2 ! 0) { return false; } int subsetTarget (total target) / 2;这里有个容易踩的细节target 可能是负数所以取绝对值判断但 subsetTarget 一定是非负的因为 total target 0 已经被第一个条件保证了。4. 动态规划实现与滚动数组优化4.1 二维 DP 的正确写法子集和问题的布尔 DP 是很经典的模板。定义 dp[i][j] 表示“处理完前 i 个元素时是否存在一种选法使和为 j”。状态转移只考虑当前元素拿或不拿dp[i][j] dp[i-1][j] || dp[i-1][j - nums[i-1]]初始条件是 dp[0][0] true表示一个元素都不选时和为 0 这件事一定成立。二维写法的好处是直观适合在讲解时展示状态含义vectorvectorbool dp(n 1, vectorbool(subsetTarget 1, false)); dp[0][0] true; for (int i 1; i n; i) { for (int j 0; j subsetTarget; j) { dp[i][j] dp[i-1][j]; if (j nums[i-1]) { dp[i][j] dp[i][j] || dp[i-1][j - nums[i-1]]; } } } return dp[n][subsetTarget];这段代码的时间复杂度是 O(n * subsetTarget)空间复杂度 O(n * subsetTarget)。当 nums.size() 比较小但 sum 很大时比如 n200、sum100000时间上可以接受但二维 bool 数组占 200 * 100001 个字节也就是约 20MB勉强还行如果 input 更极端就必须做空间优化。4.2 一维滚动数组与倒序更新的原因仔细观察转移方程第 i 行的状态只依赖第 i-1 行所以完全可以用一维数组滚动更新。核心代码如下vectorbool dp(subsetTarget 1, false); dp[0] true; for (int num : nums) { for (int j subsetTarget; j num; --j) { dp[j] dp[j] || dp[j - num]; } } return dp[subsetTarget];这里有一段我在学习时很长时间没想明白的细节为什么内层循环必须从大到小我最初写成从 num 到 subsetTarget 的正序遍历然后发现结果变成了“每个元素可以被选多次”也就是完全背包的效果。原因在于正序遍历时dp[j - num] 可能已经在当前本轮循环中被更新过等价于把同一个 num 用了两次而倒序遍历时j - num 小于 j在本轮循环里还没被更新拿到的仍然是上一轮的状态。这正好保证了“每个元素只用一次”符合 0/1 背包的语义。提示如果你以后做“数字可以重复使用”的题目比如硬币无限量的组合问题就反过来用正序遍历。判断用正序还是倒序本质是判断元素是否允许复用这个规律适用于所有背包类 DP。实测下来一维滚动数组之后空间降为 O(subsetTarget)代码也精简不少。对于存在性问题bool 数组的好处是内存紧凑cache 友好度比 int 高实际运行速度比计数版本的同规模 DP 快不少。4.3 bitset 优化把 DP 变成位运算如果 subsetTarget 比较大但还在可接受范围内有一个更狠的优化用 bitset 代替 bool 数组。核心思想是把 dp 数组看成一个二进制位集合第 i 位为 1 表示“和为 i 是可达的”。每个数字 num 的作用就是把这个集合向左移动 num 位再与原集合取或bitset100001 dp; dp[0] 1; for (int num : nums) { dp | (dp num); } return dp[subsetTarget];这个写法非常简洁而且因为 CPU 位运算天然支持 64 位甚至更宽的并行操作实际运行速度比一维 bool 数组还要快几倍。我拿 n200、sum20000 的数据对比过bool 数组 DP 大约需要几十毫秒bitset 几乎瞬时完成。bitset 的代价是需要在编译期确定最大长度。如果题目不能提前预知上限可以用变长 bitset 的库或者直接用 Python 的 int 类型模拟位集——Python 的 int 本身是无限长的左移和或运算性能也不错。但如果在 C 面试里提到 bitset一定要说清楚这个固定长度的限制否则面试官会认为你只记住了代码没理解原理。4.4 复杂度对比解法时间复杂度空间复杂度适用规模DFS 剪枝最坏 O(2^n)O(n)n 25~30二维 DPO(n * P)O(n * P)n 较小且 P 可控一维 DPO(n * P)O(P)大多数常规题目bitsetO(n * P / word_size)O(P)P 已知且可开数组这里 P (sum target) / 2。选择顺序我的经验是先做数学转化再做前置条件判断如果 P 不大小于十万量级一维 DP 足够如果 P 很大但 n 很小比如 n 25考虑回溯如果 n 在 30~40 之间且 P 非常大DP 和回溯都悬那么下一个方案才是正解。5. 数组规模变大Meet in the Middle 方案5.1 什么时候该考虑 Meet in the Middle动态规划虽然好用但它的复杂度受限于 subsetTarget 的大小。当数组元素很大、目标也很大时比如 n40、每个数最大 10^9sum 能达到 4 * 10^10这时候别说开数组连遍历一遍 P 都不可能。而回溯的 2^40 次方也约等于 1 万亿同样不可行。Meet in the Middle下文简称 MITM的思路是把数组分成两半分别枚举每一半的所有子集和然后再把两半的结果合并起来检查。枚举半段数组的所有子集复杂度是 2^(n/2)n40 时是 2^20 104 万完全可行。这个方案的适应场景非常清晰n 在 20~40 之间且 sum 很大DP 空间吃不下的时候。5.2 分半枚举 哈希匹配实现具体做法分三步。第一步把原数组对半切开第二步用位运算枚举每一半所有子集和存到两个 vector 里第三步遍历左半的每个和 left在右半集合里查找是否存在 right subsetTarget - left。vectorlong long getSubsetSums(vectorint nums, int l, int r) { vectorlong long res; int len r - l; for (int mask 0; mask (1 len); mask) { long long sum 0; for (int i 0; i len; i) { if (mask (1 i)) sum nums[l i]; } res.push_back(sum); } return res; } bool canPartition(vectorint nums, int target) { int n nums.size(); int mid n / 2; vectorlong long left getSubsetSums(nums, 0, mid); vectorlong long right getSubsetSums(nums, mid, n); sort(right.begin(), right.end()); for (long long v : left) { long long need target - v; if (binary_search(right.begin(), right.end(), need)) { return true; } } return false; }对右半排序再二分查找整体复杂度是 O(2^(n/2) * log(2^(n/2)))空间复杂度 O(2^(n/2))。我在本地测试 n40 时左右各 2^20 个子集和排序加二分查找大约几百毫秒比任何 DP 和回溯都快得多而且完全不受数值范围限制。5.3 三种核心方案怎么选我按实际解决问题的顺序排一下优先级先做数学转化和前置判断如果转换后的子集和目标 P 不大比如 10^6直接用 bitset 或一维 DP如果 P 极大但 n 30优先试试剪枝回溯如果 n 在 30~40 之间直接上 MITM超过 40 且 P 极大那通常只能靠贪心或近似算法但这类题在纯算法面试里基本不会出现。这里还要说一个细节MITM 在“计数版目标和问题”里也适用只不过合并时需要统计右半集合中某个值出现的次数可以用 unordered_map 代替排序二分。我在准备一场对性能要求很高的比赛时用过这个技巧效果比直接 DP 好很多。6. 常见问题与避坑实录6.1 “明明有解但返回 false”的四个坑第一个坑忘记判断 (sum target) 是否为偶数。我最初用 DP 跑案例时遇到 nums [1, 1, 1]target 2。sum 3(sum target) 5无法被 2 整除理论上应该返回 false但如果不提前校验subsetTarget 会被算成 2DP 可能错误地返回 true 或出现越界逻辑。这类问题在单元测试里很容易被漏掉因为大部分测试数据都是设计好的偶数情况。第二个坑一维 DP 的遍历顺序写反。前面反复强调过正序遍历会让每个元素被复用多次导致“明明不加这个数就能凑出来结果加了两次反而也能凑出来”之类的虚真结果。排查方法很简单如果 n 很小把所有部分和打出来看很容易发现重复使用了某个元素。第三个坑目标值超出了所有元素之和。这个其实在前置条件判断里已经处理了但如果你改造成别的变体比如数组里有负数判断条件就要改成 abs(target) 与 abs(sum) 的关系千万别照搬。第四个坑数组里有 0 时回溯递归栈爆炸。0 加正号和负号结果一样但 DFS 会把它当成两个分支递归下去相当于白白翻倍搜索空间。处理方式是在递归前把 0 单独统计只递归非零元素最后判断 0 的个数对结果有没有影响——事实上 0 对 sum 不影响所以结果直接由非零部分决定。6.2 值得提前准备的边界测试用例测试用例期望结果说明nums [], target 0true空集和为 0nums [0], target 0true0 可选可不选都为 0nums [0, 0, 0], target 0true多个 0 不影响nums [1], target 2falsetarget 超过 sumnums [1, 1, 1], target 2false无法整除直接排除nums [3, 5, 8], target 16false所有组合都凑不出 16这些用例里最容易出问题的是 nums [0, 0, 0], target 0。如果用的是“选或不选”模型0 也有选和不选两种选择最终一定存在某种选法使和为 0所以答案是 true。但有些实现把所有 0 忽略后直接返回 dp[subsetTarget]这时候 subsetTarget 0dp[0] 本来就是 true所以结果也是 true不会出错。真正危险的是回溯实现0 会产生大量重复分支但最终能返回只是慢如果还加了“跳过 0”的剪枝反而要注意别把问题跳没了。6.3 面试官常见的追问与变体我归纳了四个高频追问面试前自己过一遍会很有底。第一个如果数字可以重复使用怎么改这相当于把 0/1 背包改成完全背包核心变化就是一维 DP 内层遍历改成正序其它逻辑完全相同。第二个如果要输出一种具体的组合方案怎么做在 DP 记录布尔可达状态的同时额外维护一个 parent 数组标记转移到当前位置的前一个位置最后从 target 反推回去。注意选择“不选”和“选”两条路径都要记录否则反推会乱。第三个如果数组允许负数呢原问题转化公式中 sum 的含义变成正数绝对值之和target 变成绝对值偏移量推导仍然成立但要额外处理数组偏移。这个问题比较刁钻我面试时被问过一次当场推公式推了很久。第四个如果题目改成“能否把数组分成两个和相等的子集”怎么做这就是经典的 Partition Equal Subset Sum本质上等价于子集和问题取 target sum / 2先判断 sum 是否为偶数然后跑 DP 即可。会了目标和问题这道题基本是送分题。7. 我的一点个人体会把这几种解法都写熟之后我最大的感受是存在性问题虽然看起来只是“计数问题去掉计数”但它的价值在于逼你重新思考信息量的边界。计数版本必须遍历所有可能性而存在性版本允许你随时停手这种“提前终止”思维在工程里也很常见——比如缓存系统判断 key 是否存在、图算法判断两个节点是否连通都是同一个逻辑内核。我自己在刷题和面试时形成的习惯是拿到题目先问一句“到底是判断存在还是统计数量”这句话能决定整个解法的方向。如果只是判断存在优先考虑布尔 DP 和位运算因为它们不仅快而且代码极短只有 n 特别大且值域特别散时才考虑 MITM。希望这篇拆解能帮你在下一次遇到这类题目时少走几个我当年走过的弯路。
