【Day 61 】2024-06-07 - 416. 分割等和子集

[azl397985856]

416. 分割等和子集

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/partition-equal-subset-sum/

前置知识

暂无

题目描述

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

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

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].
 

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

[pandapls]

数组总和必须是偶数，因为只有偶数才能平分成两个和相等的子集 如果数组中的最大值大于目标和（总和的一半），则无法分成两个和相等的子集 动态规划方法通过构建一个布尔数组，记录是否存在某个和的子集，来判断是否可以分成两个和相等的子集

var canPartition = function(nums) {
    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) {
        return false;
    }
    const target = Math.floor(sum / 2);
    if (maxNum > target) {
        return false;
    }
    const dp = new Array(target + 1).fill(false);
    dp[0] = true;
    for (const num of nums) {
        for (let j = target; j >= num; --j) {
            dp[j] = dp[j - num] || dp[j] ;
        }
    }
    return dp[target];
};

[lxy1108]

python 3代码

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sumval = sum(nums)
        if sumval%2==1:
            return False
        target = sumval//2
        cache = set()
        for num in nums:
            tmp = set()
            for c in cache:
                if c+num==target:
                    return True
                tmp.add(c+num)
            cache = cache.union(tmp)
            if num == target:
                return True
            cache.add(num)
        return False

[zhiyuanpeng]

class Solution: def canPartition(self, nums: List[int]) -> bool: target = sum(nums) // 2 if target + target != sum(nums): return False dp = [False] * (target + 1) dp[0] = True

    for i in range(1, len(nums) + 1):
        for j in range(target, 0, -1):
            if dp[j] or (j - nums[i - 1] > -1 and dp[j - nums[i - 1]]):
                dp[j] = True
    return dp[-1]

[Dtjk]

class Solution { public boolean canPartition(int[] nums) { int n = nums.length; if (n < 2) { return false; } int sum = 0, maxNum = 0; for (int num : nums) { sum += num; maxNum = Math.max(maxNum, num); } if (sum % 2 != 0) { return false; } int target = sum / 2; if (maxNum > target) { return false; } boolean[] dp = new boolean[target + 1]; dp[0] = true; for (int i = 0; i < n; i++) { int num = nums[i]; for (int j = target; j >= num; --j) { dp[j] |= dp[j - num]; } } return dp[target]; } }