企业官网建设流程全解析

LeetCode 416. 分割等和子集

解题思路

核心转化：0-1 背包问题

1. 先求数组总和 sum，若为奇数，直接返回 false（无法平分）
2. 目标值 target = sum / 2，问题转化为：能否从数组中选出若干个数，使它们的和恰好为 target
3. 每个数字只能使用一次 → 0-1 背包

代码实现（一维 DP，推荐）

classSolution{publicbooleancanPartition(int[]nums){intsum=0;for(intnum:nums)sum+=num;// 总和为奇数，无法平分if((sum&1)==1)returnfalse;inttarget=sum/2;// dp[j] 表示：能否从数组中选出若干个数使和为 jboolean[]dp=newboolean[target+1];dp[0]=true;for(intnum:nums){// 必须倒序遍历：保证每个数只能用一次（0-1 背包）for(intj=target;j>=num;j--){dp[j]=dp[j]||dp[j-num];}}returndp[target];}}

关键点说明

· 倒序遍历 j：这是 0-1 背包的精髓。如果正序遍历，dp[j - num] 可能已经在本轮被更新过，导致同一个数字被重复使用（变成完全背包）。
· 提前剪枝：可选优化——如果某个 num > target，可以直接跳过（但一般不影响正确性，只是省点计算）。

复杂度

· 时间复杂度：O(n × target)，其中 n = nums.length，target = sum / 2
· 空间复杂度：O(target)

其他实现方式

方式一：二维 DP（便于理解）

classSolution{publicbooleancanPartition(int[]nums){intsum=0;for(intnum:nums)sum+=num;if((sum&1)==1)returnfalse;inttarget=sum/2;intn=nums.length;// dp[i][j]: 前 i 个数能否凑出和为 jboolean[][]dp=newboolean[n+1][target+1];for(inti=0;i<=n;i++)dp[i][0]=true;for(inti=1;i<=n;i++){for(intj=1;j<=target;j++){if(j<nums[i-1]){dp[i][j]=dp[i-1][j];}else{dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]];}}}returndp[n][target];}}

方式二：BigInteger 位运算（巧妙写法）

把「能否凑出和为 x」用二进制第 x 位表示，bits |= bits << num 就是"选/不选"当前数字的所有组合：

importjava.math.BigInteger;classSolution{publicbooleancanPartition(int[]nums){intsum=0;for(intnum:nums)sum+=num;if((sum&1)==1)returnfalse;BigIntegerbits=BigInteger.ONE;// 第 0 位为 1for(intnum:nums){bits=bits.or(bits.shiftLeft(num));// 选或不选}returnbits.testBit(sum/2);}}

方式三：long 数组手写 bitset（性能更好）

classSolution{publicbooleancanPartition(int[]nums){intsum=0;for(intnum:nums)sum+=num;if((sum&1)==1)returnfalse;inttarget=sum/2;intsize=target/64+1;long[]dp=newlong[size];dp[0]=1L;// 第 0 位为 1for(intnum:nums){intwordShift=num/64;intbitShift=num%64;if(bitShift==0){for(inti=size-1;i>=wordShift;i--){dp[i]|=dp[i-wordShift];}}else{for(inti=size-1;i>=wordShift;i--){longprev=dp[i-wordShift]<<bitShift;if(i-wordShift-1>=0){prev|=dp[i-wordShift-1]>>>(64-bitShift);}dp[i]|=prev;}}}return(dp[target/64]&(1L<<(target%64)))!=0;}}

推荐

优先使用一维 DP（第一段代码）：逻辑最清晰、面试最常考、理解 0-1 背包倒序遍历是核心考点。位运算版本适合追求性能或作为亮点展示。

延伸

· LeetCode 494. 目标和：同样转为子集和问题，但要求计数 → DP 计数
· LeetCode 698. 划分为 k 个等和子集：本题的加强版（k 个子集）