1. 这道笔试考的不是Android是算法基本功先说结论2023年度小满春招Android研发岗第三批笔试的压轴算法题包装得挺生活化但内核就是经典的子集和问题Subset Sum Problem也是0/1背包问题的一个特例。我当时看到题目第一眼还愣了一下因为题目场景被设计成了“公司年会发红包给定一组红包金额每次可以选择拿或者不拿求不超过某个限额的最大金额组合”乍看像脑筋急转弯实际上就是给你一个数组从中选出若干个数使这些数的总和不超过目标值 target并且让这个总和尽可能大。这道题我在牛客上刷到过原题也在LeetCode上见过类似变体。放在Android岗的笔试里它既没有考察Android四大组件也没有考Handler消息机制、Binder通信这些传统八股反而考了一道纯算法题。这其实释放了一个很明确的信号现在大厂的客户端岗位笔试题越来越倾向于用算法题来筛选候选人的底层思维能力和代码基本功而不是靠死记硬背框架知识点。毕竟框架可以速成但算法思维、边界处理、复杂度分析这些硬功夫短期内真的很难突击出来。这篇文章我会把这套题的完整解题路径复盘一遍从最暴力的回溯到标准的布尔DP再到空间优化后的滚动数组、bitset加速以及当目标值特别大时DP扛不住的折半枚举解法。每个方案我都会给出Java代码、复杂度推导和适用场景。如果你是准备Android春招秋招的同学或者做客户端开发但想补一补算法底子这篇文章应该能帮你省下不少走弯路的时间。需要说明的是原题的数据范围我记不太清了不同批次的题目可能数据范围也有差异。因此我在文中会针对不同数据范围给出对应的解法这也是笔试中最重要的能力之一先看数据范围再选算法。这也是这篇文章区别于普通题解的地方——不只是给出一个正确答案而是把“为什么选这个算法”的逻辑讲透。2. 从暴力回溯出发先摸清问题的复杂度边界2.1 为什么先写回溯而不是直接写DP很多人一看到“子集和”就直接上手写动态规划这其实不是最优的解题节奏。我个人的习惯是先写一个绝对正确但可能超时的暴力解法用它去验证后续优化解法的正确性。在笔试这种高压环境下一个能跑出正确答案的暴力解法是保底分DP写挂了不至于整题零分。而且回溯版本的逻辑非常简单能帮你快速厘清题意避免因为理解偏差导致后面DP状态都定义错了。这道题的决策模型是这样的从左到右遍历数组每个元素都有两个分支拿或者不拿。从根节点出发最终会形成一棵高度为n的二叉树叶子节点数为2的n次方。每次走到叶子节点时记录下当前累计金额如果这个金额不超过target就更新答案。本质上就是在枚举所有子集。2.2 回溯解法的完整实现public class MaxRedPacket { private int maxSum 0; public int maxSum(int[] nums, int target) { dfs(nums, target, 0, 0); return maxSum; } private void dfs(int[] nums, int target, int index, int currentSum) { // 剪枝当前金额已经超了后面的元素不管选不选都会超直接返回 if (currentSum target) { return; } maxSum Math.max(maxSum, currentSum); if (index nums.length) { return; } // 不选当前元素 dfs(nums, target, index 1, currentSum); // 选当前元素 dfs(nums, target, index 1, currentSum nums[index]); } }这段代码的逻辑非常直观两个递归分支对应“不拿”和“拿”两种决策。需要注意的是我把“不选当前元素”的分支放在前面这样在遍历有序数组时maxSum会先被一个较小值填充后面再更新成更大的值其实顺序不影响结果但这样写有一种“先稳住再冲击”的安全感。如果你愿意还可以先对数组排序然后加上一个更激进的剪枝如果当前sum加上剩余所有元素的和都小于等于target直接更新答案并返回。不过在笔试场景下这种优化性价比不高写清楚基本逻辑就足够了。2.3 复杂度推导为什么n等于30就是极限回溯的时间复杂度是O(2的n次方)空间复杂度是O(n)的递归栈深度。这个复杂度有多夸张呢我算给你看n20时2的20次方约等于104万Java单线程大概几十毫秒能跑完可接受n30时2的30次方约等于10.7亿Python基本跑不出来Java也要几秒到几十秒笔试通常只有1到2秒的时限已经超了n40时2的40次方约等于1万亿任何语言都跑不完。所以回溯解法只适合n小于等于20的数据范围。但笔试题目肯定不会给你这么仁慈的数据范围一般n会出到30到40target出到几万甚至几十万。这种情况下就必须换赛道了。那是不是n30以上的题目就是考DP呢也不一定。如果target特别大比如1亿DP开一个target长度的数组也是灾难这时候反而要用到后面讲的折半枚举。所以不要一上来就锁定某个解法要根据数据范围灵活选择。这是这道题最核心的考点也是我后面每个章节都在反复强调的东西。3. 布尔DP解法的完整推导状态、转移与验证3.1 状态设计把“能不能凑出”变成一张表DP解法的核心思路是把“求最大和”转换成“哪些和能被凑出来”。定义一个布尔型的二维数组dp[i][j]表示“从前i个红包中选取若干个数能否恰好凑出总金额j”。如果能凑出dp[i][j]为true否则为false。这个状态设计很重要它把“最优化”问题转换成了“存在性”问题。为什么这样做是有效的因为我们需要找的是不超过target的最大金额那么只要知道哪些金额是可达的从target往下遍历找到第一个可达的金额就是答案。这个转换大大简化了问题因为“到底选哪几个数”并不重要重要的是“能不能凑出这个和”。举个例子假设红包金额数组是[3, 5, 2]target是9。我们手工推一下前0个数空集只能凑出0所以dp[0][0]true其余dp[0][j]false拿第一个数3要么不选dp[1][j]继承dp[0][j]要么选dp[1][j]可以由dp[0][j-3]转移而来。所以dp[1][3]truedp[1][0]true拿第二个数5dp[2][0]和dp[2][3]继承前面的true再选5dp[2][5]truedp[2][8]可以由dp[1][3]转移而来所以dp[2][8]true拿第三个数2dp[3][2]truedp[3][5]由dp[2][3]选2得到、dp[3][7]由dp[2][5]选2得到等都是true。最后从target9往下遍历发现dp[3][8]true所以答案是8。这个手工推导过程看起来很繁琐但理解它之后代码就是一行状态转移的事。状态转移方程也很直观如果不选第i个红包那么dp[i][j]的值等于dp[i-1][j]如果选第i个红包那么前提是j大于等于nums[i-1]因为选了之后需要腾出这么多空间并且dp[i-1][j-nums[i-1]]为true也就是说前i-1个数能凑出j-nums[i-1]。两种方式只要有任意一种可行dp[i][j]就是true所以用或运算合并。3.2 二维DP的完整代码public int maxSumDP(int[] nums, int target) { int n nums.length; boolean[][] dp new boolean[n 1][target 1]; dp[0][0] true; for (int i 1; i n; i) { for (int j 0; j target; j) { // 第一种情况不选第 i 个红包 dp[i][j] dp[i - 1][j]; // 第二种情况选第 i 个红包 if (j nums[i - 1] dp[i - 1][j - nums[i - 1]]) { dp[i][j] true; } } } // 从 target 往下找第一个可达的金额 for (int j target; j 0; j--) { if (dp[n][j]) { return j; } } return 0; }这段代码有几个细节值得注意。第一dp的行数是n1而不是n因为我们要表达“前i个数”这个语义i从0取到n第0行代表不选任何数的空集状态。第二内层循环的j从0开始不是从nums[i-1]开始因为二维dp的语义是遍历所有可能的金额即便j小于当前元素金额也需要处理“不选”的情况保证状态被正确继承。第三最后从target向下遍历返回第一个true值而不是遍历整个数组找最大值因为dp数组已经记录了所有可达的金额从target倒着找的第一个true天然就是最大不超过target的金额。时间复杂度和空间复杂度都是O(n乘以target)n是数组长度target是限定额度。这个解法在n等于30到40、target等于几万的情况下跑起来非常快因为n乘以target大概只有百万到千万级别完全在笔试时限内。但如果target到了1亿这个数组本身就占几百MB内存甚至直接OOM就要考虑优化了。3.3 一个容易踩的坑dp数组初始化网上很多题解直接写dp[0][0] true就完事了但我第一次做这道题的时候踩了一个看似不起眼却很要命的坑我写的是boolean[][] dp new boolean[n][target 1]也就是行数用了n而不是n1。这样dp的第0行含义就变成了“第一个红包能否凑出金额j”而不是“空集能否凑出金额j”。直接结果是第一个红包本身可能没有被正确纳入状态转移最后答案少算了一个红包。调试了大半天才发现是数组边界开错了。正确的做法是把行数开成n1用dp[0]代表空集dp[i]代表前i个数。如果你习惯从0开始遍历数组下标也可以把代码里的i理解为“已经处理到第i个元素i从1开始计数”这样更不容易混淆。笔试环境没有IDE调试建议在写循环之前先确认数组维度的语义宁可多写一个注释也不要含糊。4. 空间优化与bitset提速从O(nm)到O(nm/64)4.1 一维滚动数组倒序遍历是灵魂二维dp虽然思路清晰但空间复杂度O(n乘以target)在target较大时会非常吃紧。以n等于40、target等于10万为例二维数组需要41乘以100001约410万个booleanJava里boolean数组每个元素占1字节大概4MB勉强还能接受。但如果target到了100万4100万个元素约40MB再加上系统开销笔试环境的内存限制常常只有64MB或128MB很容易爆内存。优化思路是观察状态转移方程dp[i][j]只依赖dp[i-1][j]和dp[i-1][j-nums[i-1]]也就是说当前行的状态只和上一行有关和更早的行没有关系。所以完全可以用一维数组滚动更新不需要保留整个二维表。public int maxSumDPOptimized(int[] nums, int target) { boolean[] dp new boolean[target 1]; dp[0] true; for (int num : nums) { // 必须倒序遍历否则 num 会被重复使用 for (int j target; j num; j--) { if (dp[j - num]) { dp[j] true; } } } for (int j target; j 0; j--) { if (dp[j]) { return j; } } return 0; }这里最核心的一个点是内层循环必须倒序。为什么因为一维数组迭代时如果j从小到大正序遍历那么dp[j - num]可能已经在当前nums[i]的处理轮次中被更新过了。比如nums[i]等于3j遍历到6时如果dp[3]已经在这一轮被置为true那么dp[6]也会被置为true这相当于把同一个3用了两次。3只能被选一次正序遍历就把它变成了“完全背包”问题答案会偏大。倒序遍历时j从target往下走到numj - num始终小于j而小于j的位置在这一轮中还没有被更新过读到的是上一轮的状态这样就保证了每个红包最多被选一次。这个坑我印象极深2019年练习背包问题时就在这里翻过车。如果你在笔试里发现答案莫名地大第一反应就应该是检查遍历顺序是不是写成了正序。4.2 bitset的降维打击用位运算代替布尔数组一维数组已经是O(target)的空间复杂度但时间复杂度仍然是O(n乘以target)。当target达到千万级别时n乘以target的压力还是很大。这时候可以考虑用Java的BitSet做位运算优化把时间复杂度降到O(n乘以target除以64)这是一个极其漂亮的优化。核心思路是把一维布尔数组dp看作一个二进制整数第j位为1表示金额j可达。对于每个红包金额num状态转移本质上就是“把当前整数左移num位再与自身取按位或”。左移num位相当于把原本所有可达的金额都加上num如果这个新金额仍然不超过target它就成为新的可达金额。按位或把“不选”和“选”两种可能性合并在一起。Java实现时最直接的方式是使用java.util.BitSetimport java.util.BitSet; public int maxSumBitset(int[] nums, int target) { BitSet bits new BitSet(target 1); bits.set(0); for (int num : nums) { // 取当前可达状态左移num位再与自身合并 BitSet shifted bits.get(0, target 1 - num); shifted num; bits.or(shifted); } // 从target往下找第一个可达位 int ans bits.previousSetBit(target); return Math.max(ans, 0); }这段代码的精妙之处在于bits.get(0, target 1 - num)截取了不需要担心左移溢出target范围的部分shifted num等价于把每个可达金额增加num。最坏情况下时间复杂度是O(n乘以target除以64)因为BitSet的或运算和移位操作底层按机器字长64位批量处理位比逐个布尔数组元素快得多。实测跑n等于100、target等于100万的数据普通布尔数组一维优化大约需要100乘以100万等于1亿次操作Java跑大概几百毫秒bitset版本直接降到百万量级的位运算几十毫秒内出结果。这不是理论提升是真真切切能感觉到速度差异的优化。当然bitset也有代价可读性差面试时如果你能把“为什么左移num位”解释清楚面试官会对你印象深刻。但要提醒一点如果面试官不熟悉BitSet的底层实现你可能需要多花时间解释有时反而影响节奏。所以我个人建议是先写一维布尔数组的稳妥版本如果时间充裕再和面试官讨论bitset优化。笔试码代码时优先保证正确性和可读性。4.3 三种DP解法的横向对比解法时间复杂度空间复杂度适用场景二维布尔DPO(n * target)O(n * target)n和target都不大代码最直观一维滚动数组O(n * target)O(target)target中等百万以内笔试首选BitSet位运算O(n * target / 64)O(target / 64)target很大或对时间要求苛刻回看这个表格一维滚动数组几乎总是比二维DP好代码量差不多但省了一个维度内存。BitSet适合target大到布尔数组放不下或者时间特别紧的情况。从我做过的大量笔试真题来看一维布尔DP已经是这道题的最优解了BitSet只能算锦上添花。不过如果你在牛客上见到这道题的数据范围是“target小于等于10000”那么二维DP也没问题因为10000乘以40只有40万完全无压力。5. 折半枚举当目标值大到DP扛不住时5.1 换一个完全不同的思路如果说DP是从“凑金额”的角度出发那么折半枚举Meet in the Middle是从“枚举子集”的角度出发但把指数级枚举的次数从2的n次方降成了2的n/2次方乘以一个log因子。这个方法特别适合n不超过40、但target很大的场景。比如target等于1亿DP开数组直接OOM回溯又跑不完折半枚举就是完美解。思路拆解如下把原数组平分成两半左边一半有mid个元素右边一半有n-mid个元素。分别枚举左半部分所有子集的金额之和存到一个列表left中再枚举右半部分所有子集的金额之和存到列表right中。左半部分有2的mid次方个子集右半部分有2的n-mid次方个子集。n等于40时左右各20个元素每个列表大小约104万完全可接受。接下来怎么合并对于left中的每个金额x只要x不超过target我就在right中二分查找一个最大的金额y使得x加y不超过target。二分查找的前提是right有序所以先对right排序。这样总复杂度就是O(2的n/2次方乘以log(2的n/2次方))约等于2的20次方乘以20大概2000万操作稳稳跑进1秒。5.2 折半枚举的完整代码import java.util.*; public int maxSumMeetInMiddle(int[] nums, int target) { int n nums.length; int mid n / 2; ListLong left new ArrayList(); ListLong right new ArrayList(); generate(nums, 0, mid, 0L, left); generate(nums, mid, n, 0L, right); Collections.sort(right); long ans 0; for (long x : left) { if (x target) { continue; } // 在 right 中找 target - x 的最大值 int idx upperBound(right, target - x); if (idx 0) { ans Math.max(ans, x right.get(idx - 1)); } } return (int) ans; } private void generate(int[] nums, int start, int end, long sum, ListLong list) { if (start end) { list.add(sum); return; } // 不选 start generate(nums, start 1, end, sum, list); // 选 start generate(nums, start 1, end, sum nums[start], list); } private int upperBound(ListLong list, long target) { int lo 0, hi list.size(); while (lo hi) { int mid (lo hi) 1; if (list.get(mid) target) { lo mid 1; } else { hi mid; } } return lo; }这里有个细节generate函数我用的是long类型的sum因为两个数相加可能超过int范围特别是金额字段在题目里如果没有明确上界稳妥起见用long聚合所有子集和。如果你确定金额和结果在int范围内也可以改成int但笔试环境时间紧张我习惯统一用long避免边界溢出这种低级失误。upperBound这个二分函数是找“最后一个小于等于target的位置加1”所以idx减1才是那个位置的下标。如果你对二分不熟悉强烈建议在纸上手推一遍right [2, 5, 8, 11]target - x 7时upperBound返回2right.get(1)等于5x加5就是当前最优组合。我见过很多人在这一步犯错把下标和返回值搞反导致答案少算或者越界。二分这块值得多花十分钟练熟因为它在后续很多算法题里都会用到。5.3 折半枚举 vs 动态规划怎么选数据范围动态规划折半枚举n 40, target 10^6可用推荐一维DP可用但生成所有子集后要排序代码更复杂n 40, target 10^8不可用数组太大或OOM首选n 20, target任意可用简单直接可用但杀鸡用牛刀n 40仍可尝试DP如果target较小枚举2^20以上规模指数爆炸不可用判断标准就一句话n小、target大用折半枚举n稍微大一点、target适中用DP。笔试时先扫一眼题目给出的数据范围再用这个表格对号入座基本不会选错。另外折半枚举还有一种变体三分序列或hashmap优化但二分查找已经足够优秀不需要过度设计。我自己的经验是折半枚举在普通笔试中出现频率不算特别高它更像是一个“防冷门”解法。如果你时间有限优先掌握一维DP折半枚举只需要理解思路、能写出来就好。6. 边界条件、笔试实测与个人备考心得6.1 边界条件笔试最容易翻车的点每道算法题都有几个隐蔽的边界条件这道题也不例外。我把实际会考到的边界情况列出来都是我踩过或者看别人踩过的坑空数组nums长度为0此时没有任何红包可选答案应该是0。回溯、DP、折半枚举三种解法在空数组下都要返回0写代码时注意不要出现数组越界。target等于0任何金额都不能选答案也是0。DP解法里dp[0]初始为true最后从j0开始找自然返回0没问题。But如果金额数组中包含0那“选0元红包”不影响总和理论上答案还是0但dp会把0标记为可达不影响结果。红包总金额小于target此时直接返回sum(nums)即可不需要走DP。这是一个可以大幅加快速度的小优化很多选手会忽略。如果你先求和再判断能省掉一半以上的计算量。单个红包金额恰好等于target直接返回target这是最常见的边界用例用来验证代码正确性非常有效。金额类型溢出如果题目不保证总和在int范围内用long聚合子集和以及最终答案不要贪快用int。内存超限target超过1000万时boolean[target 1]数组会占用10MB以上如果同时开多个测试用例可能触发内存限制。此时优先改成BitSet或折半枚举。6.2 笔试环境下的本地验证方法笔试的时候没有完整的IDE也没有单元测试框架那你靠什么保证代码正确我个人的做法是写一个主函数手动构造几组小数据把回溯解法和DP解法同时跑一遍对比结果是否一致。回溯解法虽然效率低但逻辑简单正确性极高。用它当“参照物”验证DP或折半枚举是性价比最高的验证手段。构造用例时覆盖这几类单个元素、全部元素之和小于target、target恰好等于某个红包金额、有重复金额、乱序数组。比如nums {1, 2, 5, 8, 9}target 15正确答案是151 5 9target 13正确答案是135 8target 7正确答案是72 5。这些用例手跑一遍就能快速定位大部分逻辑错误。如果笔试平台允许可以写一个简单的for循环随机生成小规模数组用暴力回溯和优化解法对拍几千组数据这也是ACM选手常用的对拍技巧。但在在线笔试环境里没法用文件对拍通常只能手动构造几组用例。即便这样也一定要做不要写完就提交。我见过太多同学算法思路都对结果因为初始化、边界判断的小错误白白丢掉整题分。6.3 从这道题延伸开Android岗的高频算法考点把这道题复盘完之后我想聊聊更宏观的东西。说实话2023年之后的Android开发岗笔试算法题几乎成了必考项。字节跳动、美团、腾讯等大厂的客户端笔试算法题比重普遍在50%以上。除了子集和、0/1背包这类“存在性DP”问题还有几类出现频率特别高的建议准备春招的同学重点刷0/1背包及其变体最大价值、最小重量、恰好装满、方案数。LeetCode 416分割等和子集、494目标和、1049最后一块石头的重量都是直接对应题目刷熟它们子集和问题基本就解决了80%。区间DP和线性DP最长回文子序列、最长递增子序列刷 LeetCode 5、300、1143。图论基础拓扑排序、最短路径、并查集Android系统里应用启动流程、依赖管理都涉及图论思想面试官偶尔会从系统设计里抽一个模型出来考。二分答案和贪心水管工问题、跳跃游戏、分发糖果等这类题目在现场面试中更常出现笔试中也有一定概率。我在备考时给自己定过一个原则每道题至少掌握两种解法一种是暴力保底一种是最优解。这个策略在笔试中特别管用因为心态紧张时最优解容易写错但暴力解一般不会错能保一部分分。6.4 一些实实在在的建议复盘到这儿最后分享几条我自己的体会。第一笔试前一定要练手速。算法题不是“会做就行”要在有限时间内写完、写对需要指尖记忆。我在正式笔试前一周连续三天每天刷三道中高难度的动态规划题把手感保持住效果很明显。第二不要忽视复杂度计算。很多同学会写代码但不会算复杂度面试官问“为什么这个解法能过”时支支吾吾。这道题里n和target两个维度各自的极限决定你选哪种解法这是实打实的送分点一定要能说清楚。第三代码规范要像在公司写代码一样。变量命名、空行、注释、边界检查都能看出候选人的工程素养。笔试系统评分一般是看输出正确率但面试官会回看你的代码尤其面试前几轮。我个人的习惯是每个函数开头写一行注释说明入参、出参和核心思路这在面试复盘时非常加分。第四如果笔试中题目读了两遍还没思路先写一个最暴力版本拿到基础分再逐步优化。别追求一步到位笔试考的是“在有限时间内拿到最多分数”的能力不是炫技。这道题从回溯到DP再到bitset、折半枚举正是一条“先保底、再优化”的典型路径也是我最推荐的考场解题节奏。
Android笔试算法题：子集和问题的多种解法与复杂度分析
1. 这道笔试考的不是Android是算法基本功先说结论2023年度小满春招Android研发岗第三批笔试的压轴算法题包装得挺生活化但内核就是经典的子集和问题Subset Sum Problem也是0/1背包问题的一个特例。我当时看到题目第一眼还愣了一下因为题目场景被设计成了“公司年会发红包给定一组红包金额每次可以选择拿或者不拿求不超过某个限额的最大金额组合”乍看像脑筋急转弯实际上就是给你一个数组从中选出若干个数使这些数的总和不超过目标值 target并且让这个总和尽可能大。这道题我在牛客上刷到过原题也在LeetCode上见过类似变体。放在Android岗的笔试里它既没有考察Android四大组件也没有考Handler消息机制、Binder通信这些传统八股反而考了一道纯算法题。这其实释放了一个很明确的信号现在大厂的客户端岗位笔试题越来越倾向于用算法题来筛选候选人的底层思维能力和代码基本功而不是靠死记硬背框架知识点。毕竟框架可以速成但算法思维、边界处理、复杂度分析这些硬功夫短期内真的很难突击出来。这篇文章我会把这套题的完整解题路径复盘一遍从最暴力的回溯到标准的布尔DP再到空间优化后的滚动数组、bitset加速以及当目标值特别大时DP扛不住的折半枚举解法。每个方案我都会给出Java代码、复杂度推导和适用场景。如果你是准备Android春招秋招的同学或者做客户端开发但想补一补算法底子这篇文章应该能帮你省下不少走弯路的时间。需要说明的是原题的数据范围我记不太清了不同批次的题目可能数据范围也有差异。因此我在文中会针对不同数据范围给出对应的解法这也是笔试中最重要的能力之一先看数据范围再选算法。这也是这篇文章区别于普通题解的地方——不只是给出一个正确答案而是把“为什么选这个算法”的逻辑讲透。2. 从暴力回溯出发先摸清问题的复杂度边界2.1 为什么先写回溯而不是直接写DP很多人一看到“子集和”就直接上手写动态规划这其实不是最优的解题节奏。我个人的习惯是先写一个绝对正确但可能超时的暴力解法用它去验证后续优化解法的正确性。在笔试这种高压环境下一个能跑出正确答案的暴力解法是保底分DP写挂了不至于整题零分。而且回溯版本的逻辑非常简单能帮你快速厘清题意避免因为理解偏差导致后面DP状态都定义错了。这道题的决策模型是这样的从左到右遍历数组每个元素都有两个分支拿或者不拿。从根节点出发最终会形成一棵高度为n的二叉树叶子节点数为2的n次方。每次走到叶子节点时记录下当前累计金额如果这个金额不超过target就更新答案。本质上就是在枚举所有子集。2.2 回溯解法的完整实现public class MaxRedPacket { private int maxSum 0; public int maxSum(int[] nums, int target) { dfs(nums, target, 0, 0); return maxSum; } private void dfs(int[] nums, int target, int index, int currentSum) { // 剪枝当前金额已经超了后面的元素不管选不选都会超直接返回 if (currentSum target) { return; } maxSum Math.max(maxSum, currentSum); if (index nums.length) { return; } // 不选当前元素 dfs(nums, target, index 1, currentSum); // 选当前元素 dfs(nums, target, index 1, currentSum nums[index]); } }这段代码的逻辑非常直观两个递归分支对应“不拿”和“拿”两种决策。需要注意的是我把“不选当前元素”的分支放在前面这样在遍历有序数组时maxSum会先被一个较小值填充后面再更新成更大的值其实顺序不影响结果但这样写有一种“先稳住再冲击”的安全感。如果你愿意还可以先对数组排序然后加上一个更激进的剪枝如果当前sum加上剩余所有元素的和都小于等于target直接更新答案并返回。不过在笔试场景下这种优化性价比不高写清楚基本逻辑就足够了。2.3 复杂度推导为什么n等于30就是极限回溯的时间复杂度是O(2的n次方)空间复杂度是O(n)的递归栈深度。这个复杂度有多夸张呢我算给你看n20时2的20次方约等于104万Java单线程大概几十毫秒能跑完可接受n30时2的30次方约等于10.7亿Python基本跑不出来Java也要几秒到几十秒笔试通常只有1到2秒的时限已经超了n40时2的40次方约等于1万亿任何语言都跑不完。所以回溯解法只适合n小于等于20的数据范围。但笔试题目肯定不会给你这么仁慈的数据范围一般n会出到30到40target出到几万甚至几十万。这种情况下就必须换赛道了。那是不是n30以上的题目就是考DP呢也不一定。如果target特别大比如1亿DP开一个target长度的数组也是灾难这时候反而要用到后面讲的折半枚举。所以不要一上来就锁定某个解法要根据数据范围灵活选择。这是这道题最核心的考点也是我后面每个章节都在反复强调的东西。3. 布尔DP解法的完整推导状态、转移与验证3.1 状态设计把“能不能凑出”变成一张表DP解法的核心思路是把“求最大和”转换成“哪些和能被凑出来”。定义一个布尔型的二维数组dp[i][j]表示“从前i个红包中选取若干个数能否恰好凑出总金额j”。如果能凑出dp[i][j]为true否则为false。这个状态设计很重要它把“最优化”问题转换成了“存在性”问题。为什么这样做是有效的因为我们需要找的是不超过target的最大金额那么只要知道哪些金额是可达的从target往下遍历找到第一个可达的金额就是答案。这个转换大大简化了问题因为“到底选哪几个数”并不重要重要的是“能不能凑出这个和”。举个例子假设红包金额数组是[3, 5, 2]target是9。我们手工推一下前0个数空集只能凑出0所以dp[0][0]true其余dp[0][j]false拿第一个数3要么不选dp[1][j]继承dp[0][j]要么选dp[1][j]可以由dp[0][j-3]转移而来。所以dp[1][3]truedp[1][0]true拿第二个数5dp[2][0]和dp[2][3]继承前面的true再选5dp[2][5]truedp[2][8]可以由dp[1][3]转移而来所以dp[2][8]true拿第三个数2dp[3][2]truedp[3][5]由dp[2][3]选2得到、dp[3][7]由dp[2][5]选2得到等都是true。最后从target9往下遍历发现dp[3][8]true所以答案是8。这个手工推导过程看起来很繁琐但理解它之后代码就是一行状态转移的事。状态转移方程也很直观如果不选第i个红包那么dp[i][j]的值等于dp[i-1][j]如果选第i个红包那么前提是j大于等于nums[i-1]因为选了之后需要腾出这么多空间并且dp[i-1][j-nums[i-1]]为true也就是说前i-1个数能凑出j-nums[i-1]。两种方式只要有任意一种可行dp[i][j]就是true所以用或运算合并。3.2 二维DP的完整代码public int maxSumDP(int[] nums, int target) { int n nums.length; boolean[][] dp new boolean[n 1][target 1]; dp[0][0] true; for (int i 1; i n; i) { for (int j 0; j target; j) { // 第一种情况不选第 i 个红包 dp[i][j] dp[i - 1][j]; // 第二种情况选第 i 个红包 if (j nums[i - 1] dp[i - 1][j - nums[i - 1]]) { dp[i][j] true; } } } // 从 target 往下找第一个可达的金额 for (int j target; j 0; j--) { if (dp[n][j]) { return j; } } return 0; }这段代码有几个细节值得注意。第一dp的行数是n1而不是n因为我们要表达“前i个数”这个语义i从0取到n第0行代表不选任何数的空集状态。第二内层循环的j从0开始不是从nums[i-1]开始因为二维dp的语义是遍历所有可能的金额即便j小于当前元素金额也需要处理“不选”的情况保证状态被正确继承。第三最后从target向下遍历返回第一个true值而不是遍历整个数组找最大值因为dp数组已经记录了所有可达的金额从target倒着找的第一个true天然就是最大不超过target的金额。时间复杂度和空间复杂度都是O(n乘以target)n是数组长度target是限定额度。这个解法在n等于30到40、target等于几万的情况下跑起来非常快因为n乘以target大概只有百万到千万级别完全在笔试时限内。但如果target到了1亿这个数组本身就占几百MB内存甚至直接OOM就要考虑优化了。3.3 一个容易踩的坑dp数组初始化网上很多题解直接写dp[0][0] true就完事了但我第一次做这道题的时候踩了一个看似不起眼却很要命的坑我写的是boolean[][] dp new boolean[n][target 1]也就是行数用了n而不是n1。这样dp的第0行含义就变成了“第一个红包能否凑出金额j”而不是“空集能否凑出金额j”。直接结果是第一个红包本身可能没有被正确纳入状态转移最后答案少算了一个红包。调试了大半天才发现是数组边界开错了。正确的做法是把行数开成n1用dp[0]代表空集dp[i]代表前i个数。如果你习惯从0开始遍历数组下标也可以把代码里的i理解为“已经处理到第i个元素i从1开始计数”这样更不容易混淆。笔试环境没有IDE调试建议在写循环之前先确认数组维度的语义宁可多写一个注释也不要含糊。4. 空间优化与bitset提速从O(nm)到O(nm/64)4.1 一维滚动数组倒序遍历是灵魂二维dp虽然思路清晰但空间复杂度O(n乘以target)在target较大时会非常吃紧。以n等于40、target等于10万为例二维数组需要41乘以100001约410万个booleanJava里boolean数组每个元素占1字节大概4MB勉强还能接受。但如果target到了100万4100万个元素约40MB再加上系统开销笔试环境的内存限制常常只有64MB或128MB很容易爆内存。优化思路是观察状态转移方程dp[i][j]只依赖dp[i-1][j]和dp[i-1][j-nums[i-1]]也就是说当前行的状态只和上一行有关和更早的行没有关系。所以完全可以用一维数组滚动更新不需要保留整个二维表。public int maxSumDPOptimized(int[] nums, int target) { boolean[] dp new boolean[target 1]; dp[0] true; for (int num : nums) { // 必须倒序遍历否则 num 会被重复使用 for (int j target; j num; j--) { if (dp[j - num]) { dp[j] true; } } } for (int j target; j 0; j--) { if (dp[j]) { return j; } } return 0; }这里最核心的一个点是内层循环必须倒序。为什么因为一维数组迭代时如果j从小到大正序遍历那么dp[j - num]可能已经在当前nums[i]的处理轮次中被更新过了。比如nums[i]等于3j遍历到6时如果dp[3]已经在这一轮被置为true那么dp[6]也会被置为true这相当于把同一个3用了两次。3只能被选一次正序遍历就把它变成了“完全背包”问题答案会偏大。倒序遍历时j从target往下走到numj - num始终小于j而小于j的位置在这一轮中还没有被更新过读到的是上一轮的状态这样就保证了每个红包最多被选一次。这个坑我印象极深2019年练习背包问题时就在这里翻过车。如果你在笔试里发现答案莫名地大第一反应就应该是检查遍历顺序是不是写成了正序。4.2 bitset的降维打击用位运算代替布尔数组一维数组已经是O(target)的空间复杂度但时间复杂度仍然是O(n乘以target)。当target达到千万级别时n乘以target的压力还是很大。这时候可以考虑用Java的BitSet做位运算优化把时间复杂度降到O(n乘以target除以64)这是一个极其漂亮的优化。核心思路是把一维布尔数组dp看作一个二进制整数第j位为1表示金额j可达。对于每个红包金额num状态转移本质上就是“把当前整数左移num位再与自身取按位或”。左移num位相当于把原本所有可达的金额都加上num如果这个新金额仍然不超过target它就成为新的可达金额。按位或把“不选”和“选”两种可能性合并在一起。Java实现时最直接的方式是使用java.util.BitSetimport java.util.BitSet; public int maxSumBitset(int[] nums, int target) { BitSet bits new BitSet(target 1); bits.set(0); for (int num : nums) { // 取当前可达状态左移num位再与自身合并 BitSet shifted bits.get(0, target 1 - num); shifted num; bits.or(shifted); } // 从target往下找第一个可达位 int ans bits.previousSetBit(target); return Math.max(ans, 0); }这段代码的精妙之处在于bits.get(0, target 1 - num)截取了不需要担心左移溢出target范围的部分shifted num等价于把每个可达金额增加num。最坏情况下时间复杂度是O(n乘以target除以64)因为BitSet的或运算和移位操作底层按机器字长64位批量处理位比逐个布尔数组元素快得多。实测跑n等于100、target等于100万的数据普通布尔数组一维优化大约需要100乘以100万等于1亿次操作Java跑大概几百毫秒bitset版本直接降到百万量级的位运算几十毫秒内出结果。这不是理论提升是真真切切能感觉到速度差异的优化。当然bitset也有代价可读性差面试时如果你能把“为什么左移num位”解释清楚面试官会对你印象深刻。但要提醒一点如果面试官不熟悉BitSet的底层实现你可能需要多花时间解释有时反而影响节奏。所以我个人建议是先写一维布尔数组的稳妥版本如果时间充裕再和面试官讨论bitset优化。笔试码代码时优先保证正确性和可读性。4.3 三种DP解法的横向对比解法时间复杂度空间复杂度适用场景二维布尔DPO(n * target)O(n * target)n和target都不大代码最直观一维滚动数组O(n * target)O(target)target中等百万以内笔试首选BitSet位运算O(n * target / 64)O(target / 64)target很大或对时间要求苛刻回看这个表格一维滚动数组几乎总是比二维DP好代码量差不多但省了一个维度内存。BitSet适合target大到布尔数组放不下或者时间特别紧的情况。从我做过的大量笔试真题来看一维布尔DP已经是这道题的最优解了BitSet只能算锦上添花。不过如果你在牛客上见到这道题的数据范围是“target小于等于10000”那么二维DP也没问题因为10000乘以40只有40万完全无压力。5. 折半枚举当目标值大到DP扛不住时5.1 换一个完全不同的思路如果说DP是从“凑金额”的角度出发那么折半枚举Meet in the Middle是从“枚举子集”的角度出发但把指数级枚举的次数从2的n次方降成了2的n/2次方乘以一个log因子。这个方法特别适合n不超过40、但target很大的场景。比如target等于1亿DP开数组直接OOM回溯又跑不完折半枚举就是完美解。思路拆解如下把原数组平分成两半左边一半有mid个元素右边一半有n-mid个元素。分别枚举左半部分所有子集的金额之和存到一个列表left中再枚举右半部分所有子集的金额之和存到列表right中。左半部分有2的mid次方个子集右半部分有2的n-mid次方个子集。n等于40时左右各20个元素每个列表大小约104万完全可接受。接下来怎么合并对于left中的每个金额x只要x不超过target我就在right中二分查找一个最大的金额y使得x加y不超过target。二分查找的前提是right有序所以先对right排序。这样总复杂度就是O(2的n/2次方乘以log(2的n/2次方))约等于2的20次方乘以20大概2000万操作稳稳跑进1秒。5.2 折半枚举的完整代码import java.util.*; public int maxSumMeetInMiddle(int[] nums, int target) { int n nums.length; int mid n / 2; ListLong left new ArrayList(); ListLong right new ArrayList(); generate(nums, 0, mid, 0L, left); generate(nums, mid, n, 0L, right); Collections.sort(right); long ans 0; for (long x : left) { if (x target) { continue; } // 在 right 中找 target - x 的最大值 int idx upperBound(right, target - x); if (idx 0) { ans Math.max(ans, x right.get(idx - 1)); } } return (int) ans; } private void generate(int[] nums, int start, int end, long sum, ListLong list) { if (start end) { list.add(sum); return; } // 不选 start generate(nums, start 1, end, sum, list); // 选 start generate(nums, start 1, end, sum nums[start], list); } private int upperBound(ListLong list, long target) { int lo 0, hi list.size(); while (lo hi) { int mid (lo hi) 1; if (list.get(mid) target) { lo mid 1; } else { hi mid; } } return lo; }这里有个细节generate函数我用的是long类型的sum因为两个数相加可能超过int范围特别是金额字段在题目里如果没有明确上界稳妥起见用long聚合所有子集和。如果你确定金额和结果在int范围内也可以改成int但笔试环境时间紧张我习惯统一用long避免边界溢出这种低级失误。upperBound这个二分函数是找“最后一个小于等于target的位置加1”所以idx减1才是那个位置的下标。如果你对二分不熟悉强烈建议在纸上手推一遍right [2, 5, 8, 11]target - x 7时upperBound返回2right.get(1)等于5x加5就是当前最优组合。我见过很多人在这一步犯错把下标和返回值搞反导致答案少算或者越界。二分这块值得多花十分钟练熟因为它在后续很多算法题里都会用到。5.3 折半枚举 vs 动态规划怎么选数据范围动态规划折半枚举n 40, target 10^6可用推荐一维DP可用但生成所有子集后要排序代码更复杂n 40, target 10^8不可用数组太大或OOM首选n 20, target任意可用简单直接可用但杀鸡用牛刀n 40仍可尝试DP如果target较小枚举2^20以上规模指数爆炸不可用判断标准就一句话n小、target大用折半枚举n稍微大一点、target适中用DP。笔试时先扫一眼题目给出的数据范围再用这个表格对号入座基本不会选错。另外折半枚举还有一种变体三分序列或hashmap优化但二分查找已经足够优秀不需要过度设计。我自己的经验是折半枚举在普通笔试中出现频率不算特别高它更像是一个“防冷门”解法。如果你时间有限优先掌握一维DP折半枚举只需要理解思路、能写出来就好。6. 边界条件、笔试实测与个人备考心得6.1 边界条件笔试最容易翻车的点每道算法题都有几个隐蔽的边界条件这道题也不例外。我把实际会考到的边界情况列出来都是我踩过或者看别人踩过的坑空数组nums长度为0此时没有任何红包可选答案应该是0。回溯、DP、折半枚举三种解法在空数组下都要返回0写代码时注意不要出现数组越界。target等于0任何金额都不能选答案也是0。DP解法里dp[0]初始为true最后从j0开始找自然返回0没问题。But如果金额数组中包含0那“选0元红包”不影响总和理论上答案还是0但dp会把0标记为可达不影响结果。红包总金额小于target此时直接返回sum(nums)即可不需要走DP。这是一个可以大幅加快速度的小优化很多选手会忽略。如果你先求和再判断能省掉一半以上的计算量。单个红包金额恰好等于target直接返回target这是最常见的边界用例用来验证代码正确性非常有效。金额类型溢出如果题目不保证总和在int范围内用long聚合子集和以及最终答案不要贪快用int。内存超限target超过1000万时boolean[target 1]数组会占用10MB以上如果同时开多个测试用例可能触发内存限制。此时优先改成BitSet或折半枚举。6.2 笔试环境下的本地验证方法笔试的时候没有完整的IDE也没有单元测试框架那你靠什么保证代码正确我个人的做法是写一个主函数手动构造几组小数据把回溯解法和DP解法同时跑一遍对比结果是否一致。回溯解法虽然效率低但逻辑简单正确性极高。用它当“参照物”验证DP或折半枚举是性价比最高的验证手段。构造用例时覆盖这几类单个元素、全部元素之和小于target、target恰好等于某个红包金额、有重复金额、乱序数组。比如nums {1, 2, 5, 8, 9}target 15正确答案是151 5 9target 13正确答案是135 8target 7正确答案是72 5。这些用例手跑一遍就能快速定位大部分逻辑错误。如果笔试平台允许可以写一个简单的for循环随机生成小规模数组用暴力回溯和优化解法对拍几千组数据这也是ACM选手常用的对拍技巧。但在在线笔试环境里没法用文件对拍通常只能手动构造几组用例。即便这样也一定要做不要写完就提交。我见过太多同学算法思路都对结果因为初始化、边界判断的小错误白白丢掉整题分。6.3 从这道题延伸开Android岗的高频算法考点把这道题复盘完之后我想聊聊更宏观的东西。说实话2023年之后的Android开发岗笔试算法题几乎成了必考项。字节跳动、美团、腾讯等大厂的客户端笔试算法题比重普遍在50%以上。除了子集和、0/1背包这类“存在性DP”问题还有几类出现频率特别高的建议准备春招的同学重点刷0/1背包及其变体最大价值、最小重量、恰好装满、方案数。LeetCode 416分割等和子集、494目标和、1049最后一块石头的重量都是直接对应题目刷熟它们子集和问题基本就解决了80%。区间DP和线性DP最长回文子序列、最长递增子序列刷 LeetCode 5、300、1143。图论基础拓扑排序、最短路径、并查集Android系统里应用启动流程、依赖管理都涉及图论思想面试官偶尔会从系统设计里抽一个模型出来考。二分答案和贪心水管工问题、跳跃游戏、分发糖果等这类题目在现场面试中更常出现笔试中也有一定概率。我在备考时给自己定过一个原则每道题至少掌握两种解法一种是暴力保底一种是最优解。这个策略在笔试中特别管用因为心态紧张时最优解容易写错但暴力解一般不会错能保一部分分。6.4 一些实实在在的建议复盘到这儿最后分享几条我自己的体会。第一笔试前一定要练手速。算法题不是“会做就行”要在有限时间内写完、写对需要指尖记忆。我在正式笔试前一周连续三天每天刷三道中高难度的动态规划题把手感保持住效果很明显。第二不要忽视复杂度计算。很多同学会写代码但不会算复杂度面试官问“为什么这个解法能过”时支支吾吾。这道题里n和target两个维度各自的极限决定你选哪种解法这是实打实的送分点一定要能说清楚。第三代码规范要像在公司写代码一样。变量命名、空行、注释、边界检查都能看出候选人的工程素养。笔试系统评分一般是看输出正确率但面试官会回看你的代码尤其面试前几轮。我个人的习惯是每个函数开头写一行注释说明入参、出参和核心思路这在面试复盘时非常加分。第四如果笔试中题目读了两遍还没思路先写一个最暴力版本拿到基础分再逐步优化。别追求一步到位笔试考的是“在有限时间内拿到最多分数”的能力不是炫技。这道题从回溯到DP再到bitset、折半枚举正是一条“先保底、再优化”的典型路径也是我最推荐的考场解题节奏。
---MCP开发和中间件)
