Hard

题目描述

给你一个由正整数组成的数组 nums 和一个整数 k。

将数组分割成两个有序组，使得每个元素恰好在一个组中。如果每个组的元素和都大于或等于 k，则称该分割为优秀分割。

返回不同优秀分割的数量。由于答案可能很大，返回对 10^9 + 7 取模的结果。

如果某个元素 nums[i] 在两个分割中属于不同的组，则认为这两个分割是不同的。

示例 1：

输入：nums = [1,2,3,4], k = 4
输出：6
解释：优秀分割有：([1,2,3], [4])、([1,3], [2,4])、([1,4], [2,3])、([2,3], [1,4])、([2,4], [1,3]) 和 ([4], [1,2,3])。

示例 2：

输入：nums = [3,3,3], k = 4
输出：0
解释：对于这个数组，没有优秀分割。

示例 3：

输入：nums = [6,6], k = 2
输出：2
解释：我们可以将 nums[0] 放在第一个分割或第二个分割中。
优秀分割是 ([6], [6]) 和 ([6], [6])。

约束条件：

  • 1 <= nums.length, k <= 1000
  • 1 <= nums[i] <= 10^9

解题思路

这道题要求我们计算优秀分割的数量，其中优秀分割指两个组的元素和都大于等于k。

核心思路： 我们可以采用反向思维来解决这个问题。总的分割数量是 2^n（每个元素可以选择放入第一组或第二组），我们需要减去不符合条件的分割数量。

不符合条件的分割是指至少有一个组的和小于k的分割。设第一组元素和为sum1，第二组元素和为sum2，总和为total。由于sum1 + sum2 = total，如果sum1 < k，那么sum2 = total - sum1 > total - k。

算法步骤：

  1. 首先检查total是否小于2*k，如果是则无法形成优秀分割，返回0
  2. 使用动态规划计算第一组和小于k的分割数量
  3. 由于对称性，第二组和小于k的分割数量相同
  4. 需要减去两组和都小于k的重复计算（如果存在的话）
  5. 最终答案 = 2^n - 2 * (第一组和<k的分割数) + (两组和都<k的分割数)

DP状态定义：

  • dp[i][j] 表示前i个元素中选择一些元素使得和为j的方案数
  • 状态转移：dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]

由于nums[i]可能很大，我们需要优化空间，只考虑和小于k的情况。

代码实现

class Solution {
public:
    int countPartitions(vector<int>& nums, int k) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        long long total = 0;
        for (int num : nums) {
            total += num;
        }
        
        if (total < 2LL * k) return 0;
        
        // dp[j] = number of ways to get sum j
        vector<long long> dp(k, 0);
        dp[0] = 1;
        
        for (int num : nums) {
            for (int j = k - 1; j >= num; j--) {
                dp[j] = (dp[j] + dp[j - num]) % MOD;
            }
        }
        
        // Count partitions where first group sum < k
        long long bad = 0;
        for (int j = 0; j < k; j++) {
            bad = (bad + dp[j]) % MOD;
        }
        
        // Total partitions = 2^n
        long long total_partitions = 1;
        for (int i = 0; i < n; i++) {
            total_partitions = (total_partitions * 2) % MOD;
        }
        
        // Answer = total - 2 * bad (by symmetry, second group sum < k has same count)
        long long ans = (total_partitions - 2 * bad % MOD + MOD) % MOD;
        return ans;
    }
};

class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        total = sum(nums)
        
        if total < 2 * k:
            return 0
        
        # dp[j] = number of ways to get sum j
        dp = [0] * k
        dp[0] = 1
        
        for num in nums:
            for j in range(k - 1, num - 1, -1):
                dp[j] = (dp[j] + dp[j - num]) % MOD
        
        # Count partitions where first group sum < k
        bad = sum(dp) % MOD
        
        # Total partitions = 2^n
        total_partitions = pow(2, n, MOD)
        
        # Answer = total - 2 * bad (by symmetry)
        ans = (total_partitions - 2 * bad) % MOD
        return ans

public class Solution {
    public int CountPartitions(int[] nums, int k) {
        const int MOD = 1000000007;
        int n = nums.Length;
        long total = 0;
        foreach (int num in nums) {
            total += num;
        }
        
        if (total < 2L * k) return 0;
        
        // dp[j] = number of ways to get sum j
        long[] dp = new long[k];
        dp[0] = 1;
        
        foreach (int num in nums) {
            for (int j = k - 1; j >= num; j--) {
                dp[j] = (dp[j] + dp[j - num]) % MOD;
            }
        }
        
        // Count partitions where first group sum < k
        long bad = 0;
        for (int j = 0; j < k; j++) {
            bad = (bad + dp[j]) % MOD;
        }
        
        // Total partitions = 2^n
        long totalPartitions = 1;
        for (int i = 0; i < n; i++) {
            totalPartitions = (totalPartitions * 2) % MOD;
        }
        
        // Answer = total - 2 * bad (by symmetry)
        long ans = (totalPartitions - 2 * bad % MOD + MOD) % MOD;
        return (int)ans;
    }
}

var countPartitions = function(nums, k) {
    const MOD = 1e9 + 7;
    const n = nums.length;
    const total = nums.reduce((sum, num) => sum + num, 0);
    
    if (total < 2 * k) return 0;
    
    // dp[j] = number of ways to get sum j
    const dp = new Array(k).fill(0);
    dp[0] = 1;
    
    for (const num of nums) {
        for (let j = k - 1; j >= num; j--) {
            dp[j] = (dp[j] + dp[j - num]) % MOD;
        }
    }
    
    // Count partitions where first group sum < k
    const bad = dp.reduce((sum, count) => (sum + count) % MOD, 0);
    
    // Total partitions = 2^n
    let totalPartitions = 1;
    for (let i = 0; i < n; i++) {
        totalPartitions = (totalPartitions * 2) % MOD;
    }
    
    // Answer = total - 2 * bad (by symmetry)
    const ans = (totalPartitions - 2 * bad % MOD + MOD) % MOD;
    return ans;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n × k)
空间复杂度O(k)

说明：

  • 时间复杂度：外层循环遍历n个元素，内层循环最多遍历k次，总时间复杂度为O(n × k)
  • 空间复杂度：使用一维DP数组，长度为k，空间复杂度为O(k)

相关题目