分割等和子数组

七崽爱吃小饼干2026/02/09阅读 0

分割等和子数组

给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

codeType

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

codeType

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100

解法

function canPartition(nums: number[]): boolean {
    // 首先计算sum，如果sum是奇数则返回false
    // 如果是偶数，那么我们就要找到一些数字使得其和为target = sum / 2
    // 如果能找到则返回true
    // dp[i][j]表示 数组0-i中是否存在元素和 = j
    // 如果j >= nums[i]
    // 对于dp[i][j]有两种情况，是否选取nums[i]
    // 选取 dp[i][j] = dp[i - 1][j - nums[i]]
    // 不选取 dp[i][j] = dp[i - 1][j]
    // 如果 j < nums[i] 那么无法添加nums[i]
    // dp[i][j] = dp[i - 1][j]
    const n = nums.length;
    if (n < 2) {
        return false;
    }
    let sum = 0, maxNum = 0;
    for (const num of nums) {
        sum += num;
        maxNum = maxNum > num ? maxNum : num;
    }
    if (sum & 1) { // 通过二进制数最后一位是否是1来判断奇偶
        return false;
    }
    const target = Math.floor(sum / 2);
    if (maxNum > target) { // 最大数字超过总和的一半
        return false;
    }
    const dp = new Array(n).fill(0).map(() => new Array(target + 1).fill(false));
    for (let i = 0; i < n; i++) { // j = 0 时为true
        dp[i][0] = true;
    }
    dp[0][nums[0]] = true;
    for (let i = 1; i < n; i++) {
        const num = nums[i];
        for (let j = 1; j <= target; j++) {
            if (j >= num) {
                dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n - 1][target];
};