这道题的核心思路是正难则反——直接计算“好分区”比较困难我们转而计算“不好分区”的数量然后用总分区数减去它。解题思路1. 总分区数每个元素可以分到第一组或第二组所以总共有 2^n 种分区方式。2. 不好分区的定义至少有一组的元素和 小于 k。这包含两种情况- 第一组和 k- 第二组和 k注意两组和都 k 的情况会被重复计算需要特殊处理。3. 快速判断无解如果所有元素的总和 2*k那么无论如何分区总有一组和 k直接返回 0。4. 核心算法——0-1背包- 用 dp[j] 表示从数组中选出若干元素使其和 恰好为 j 的方案数j 的范围是 0 到 k-1。- 这是一个经典的0-1背包问题状态转移方程为dp[j] dp[j] dp[j - nums[i]] (当 j nums[i] 时)- 注意需要倒序遍历 j避免重复使用同一个元素。5. 计算不好分区数- 设 bad sum(dp[0] dp[1] ... dp[k-1])表示第一组和 k 的方案数。- 由于第一组和第二组可以互换所以不好分区数 bad * 2。- 但这里有一个细节当两组和都 k 时这种分区被算了两次第一组是A、第二组是B 和 第一组是B、第二组是A但实际上它们是同一个分区。不过题目中“好分区”要求两组和都 k所以两组和都 k 的分区本来就不可能是好分区我们只需要确保在减法中不重复扣除即可。实际上bad * 2 已经正确包含了所有至少一组和 k 的情况因为当两组和都 k 时dp 中既包含了第一组和 k 的方案也包含了第二组和 k 的方案通过互换得到所以乘以2是准确的。6. 最终答案好分区数 (总分区数 - 不好分区数 MOD) % MOD代码实现class Solution {private static final int MOD 1_000_000_007;public int countPartitions(int[] nums, int k) {long sum 0;for (int x : nums) sum x;// 如果总和小于 2*k不可能有好分区if (sum 2L * k) return 0;int n nums.length;// dp[j]选出若干元素和为 j 的方案数j kint[] dp new int[k];dp[0] 1; // 空集和为0是一种方案// 0-1背包倒序更新for (int x : nums) {for (int j k - 1; j x; j--) {dp[j] (dp[j] dp[j - x]) % MOD;}}// 计算所有和小于 k 的方案数long bad 0;for (int j 0; j k; j) {bad (bad dp[j]) % MOD;}// 不好分区数 第一组和k 或 第二组和kbad bad * 2 % MOD;// 总分区数 2^nlong total 1;for (int i 0; i n; i) {total total * 2 % MOD;}// 好分区数 总分区数 - 不好分区数return (int)((total - bad MOD) % MOD);}}复杂度分析- 时间复杂度O(n * k)其中 n 是数组长度k 是给定的阈值。- 空间复杂度O(k)使用一维滚动数组优化了空间。示例验证以 nums [1,2,3,4], k 4 为例- 总和 10 8继续计算- 背包计算得到 dp[0]1, dp[1]1, dp[2]2, dp[3]3- bad (1123)*2 14- 总分区数 2^4 16- 好分区数 16 - 14 2 不对预期是6。这里需要重新检查实际上 dp 计算的是恰好和为 j 的方案数但我们的 bad 应该统计的是小于 k 的方案数即 dp[0] dp[1] dp[2] dp[3] 7乘以2得14总分区16差为2。但预期答案是6说明有问题。问题出在当两组和都 k 时bad * 2 多算了。例如{1,2} 和 {3,4} 这种分区第一组和34这是不好的但 {1,2,3} 和 {4} 这种第一组和64第二组和44这是好的。而两组和都 k 的情况比如总和2k时不会出现所以 bad * 2 是正确的。但为什么示例结果不对因为 dp 计算的是第一组的和为 j 的方案数而 bad 应该统计的是第一组和 k 的方案数即 sum(dp[0..k-1])。但这里有一个关键点dp 中包含了第一组为空集的情况dp[0]1而空集的和为0这对应着所有元素都在第二组此时第二组和总和k因为总和2k所以第一组和k时第二组和可能2k两组和都k 的情况不可能出现所以就是 bad * 2。但示例中 bad 7bad * 2 14总分区16差为2而预期是6说明我们的 dp 计算有误。让我们重新计算 dp对于 nums [1,2,3,4]k4- 初始化dp[0]1- 处理1dp[1] dp[0] → dp[1]1- 处理2dp[2] dp[0] → dp[2]1dp[3] dp[1] → dp[3]1- 处理3dp[3] dp[0] → dp[3]2dp[2] 已处理过不对倒序j3dp[3] dp[0] → dp[3]2j2dp[2] dp[-1] 跳过j1跳过- 处理4j3dp[3] dp[-1] 跳过所以 dp [1,1,1,2]bad 1112 5bad*2 10总分区16好分区6。正确原来我之前的计算错了dp[2] 应该是1而不是2因为只有 {2} 这一种方式得到和2{1,?} 无法得到2因为1?2需要?1但只有一个1。所以代码是正确的示例验证通过。