【Day 61 】2023-08-09 - 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

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

[GuitarYs]

class Solution:
    def canPartition(self, nums) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 != 0:
            return False
        target_sum = total_sum // 2
        dp = [[False] * (target_sum + 1) for _ in range(len(nums) + 1)]
        dp[0][0] = True
        for i in range(1, len(nums) + 1):
            num = nums[i - 1]
            for j in range(target_sum + 1):
                dp[i][j] = dp[i - 1][j]
                if j >= num:
                    dp[i][j] = dp[i][j] or dp[i - 1][j - num]
        return dp[len(nums)][target_sum]

[Diana21170648]

思路

动态规划

代码

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        tar=sum(nums)//2
        if tar+tar !=sum(nums):
            return False
        dp=[False]*(tar+1)
        dp[0]=True
        for i in range(1,len(nums)+1):
            for j in range(tar,0,-1):
                if dp[j] or (j-nums[i-1]>-1 and dp[j-nums[i-1]]):
                    dp[j]=True
        return dp[-1]

复杂度分析

• 时间复杂度：O(N*N)，其中 N 为数组长度。
• 空间复杂度：O(N)

[Alexno1no2]

# 思路
# 01背包问题------能不能装满容量为target的背包

# 本题要求把数组分成两个等和的子集，相当于找到一个子集，其和为sum/2，这个sum/2就是target

# 具体步骤如下：
# 特例：如果sum为奇数，那一定找不到符合要求的子集，返回False。

# dp[j]含义：有没有和为j的子集，有为True，没有为False。

# 初始化dp数组：长度为target + 1，用于存储子集的和从0到target是否可能取到的情况。 比如和为0一定可以取到（也就是子集为空），那么dp[0] = True。

# 接下来开始遍历nums数组，对遍历到的数nums[i]有两种操作，一个是选择这个数，一个是不选择这个数。 
# －--不选择这个数：dp不变 
# --－选择这个数：dp中已为True的情况再加上nums[i]也为True。比如dp[0]已经为True，那么dp[0 + nums[i]]也是True

# 在做出选择之前，我们先逆序遍历子集的和从nums[i]到target的所有情况，判断当前数加入后，dp数组中哪些和的情况可以从False变成True。 
# （为什么要逆序，是因为dp后面的和的情况是从前面的情况转移过来的，如果前面的情况因为当前nums[i]的加入变为了True，比如dp[0 + nums[i]]变成了True，那么因为一个数只能用一次，dp[0 + nums[i] + nums[i]]不可以从dp[0 + nums[i]]转移过来。如果非要正序遍历，必须要多一个数组用于存储之前的情况。而逆序遍历可以省掉这个数组）

# dp[j] = dp[j] or dp[j - nums[i]]
# 这行代码的意思是说，如果不选择当前数，那么和为j的情况保持不变，dp[j]仍然是dp[j]，原来是True就还是True，原来是False也还是False；
# 如果选择当前数，那么如果j - nums[i]这种情况是True的话和为j的情况也会是True。比如和为0一定为True，只要 j - nums[i] == 0，那么dp[j]就变成了True。
# dp[j]和dp[j-nums[i]]只要有一个为True，dp[j]就变成True，因此用or连接两者。
# 最后就看dp[-1]是不是True，也就是dp[target]是不是True

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sumAll = sum(nums)
        if sumAll % 2:
            return False
        target = sumAll // 2

        dp = [False] * (target + 1)
        dp[0] = True

        for i in range(len(nums)):
            for j in range(target, nums[i] - 1, -1):
                dp[j] = dp[j] or dp[j - nums[i]]
        return dp[-1]

[Momogir]

#要分割成两个相等的子集，说明一个数组的元素和要为s=sum(nums)/2
# if  如果s is float，那么在整数数字列表中肯定无法得到一个整数
# else 枚举所有和为s的子集
# 暴力枚举的话复杂度为O(n * 2^n),其中系数n是sum计算的线性复杂度，空间复杂度为O(n),就是子集的长度
import numpy as np
#可以看成0-1背包问题的变形
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n=len(nums)
        s=sum(nums)
        #是奇数
        if s&1 : return False
        target=int(s/2)
        print(target)
        dp=[[False]*(target+1) for _ in range(n)]
        print(len(dp),len(dp[0]))
        #对于dp[i][j]状态的含义
        #考虑坐标区间为[0,i]的所有整数,在它们当中是否能选出一些数字，能使得这些数字之和恰好为j

        if nums[0]<=target: dp[0][nums[0]]=True
        for i in range(1,n):
            for j in range(target+1):
                # print(i,j)
                #如果不考虑当前元素,则dp[i-1][j]的值跟上一行的值一样
                try:dp[i][j]=dp[i-1][j]
                except:print('error1',i,j)

                #如果考虑当前元素，且当前元素就为j
                try:
                    if (nums[i]==j): dp[i][j]=True
                except:print('error2',i,j)

                #如果考虑当前元素，且当前元素<j
                if nums[i]<j: dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
        return dp[n-1][target]

[mo660]

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        int size = nums.size();
        for(auto i : nums){
            sum += i;
        }
        if (size < 2)
            return false;
        int target = 0;
        if (sum % 2)
            return false;
        else
            target = sum/2;
        int maxNum = *max_element(nums.begin(), nums.end());
        if (maxNum > target) {
            return false;
        }
        vector<vector<int>> dp(size, vector<int>(target + 1, 0));
        for (int i = 0; i < size; i++)
        {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        for (int i = 1; i < size; i++)
        {
            for (int j = 1; j < target+1; j++)
            {
                if (j >= nums[i])
                {
                    dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]];
                }
                else
                {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[size-1][target];
    }
};

[Fuku-L]

代码

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];
    }
}

[Beanza]

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]; } }

[snmyj]