【Day 61 】2023-04-15 - 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

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

[enrilwang]

class Solution { public: bool canPartition(vector& nums) { int sum = 0; for(int e : nums) sum += e; if(sum & 1) return false; vector d((sum>>=1)+1, false);//sum/=2 for(int i = 0 ; i < nums.size() ; i++){ for(int s = sum ; s >= 0 ; s--/int s = 0 ; s <= sum ; s++/){//从后往前，因为前面的元素我们已经求过了(i>0时确实已经求过了，i==0时我们求一遍即可，下面的代码也确实给出了i==0的情况)，可以直接用 if(!i) d/[i]/[s] = (nums[i]==s);//i==0要单独求{ nums[0]一个元素和为s } else d/[i]/[s] = d/[i-1]/[s] || (s-nums[i]>=0 ? d/[i-1]/[s-nums[i]] : false); } } return d/[nums.size()-1]/[sum];//[0,nums.size()-1]区间和为sum } };

[JiangyanLiNEU]

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        def dp(i,target ):
            if(target==0):
                return True
            if(i==len(nums) or target < 0):
                return False 
            if(self.dp[i][target] != -1 ):
                return self.dp[i][target]
            self.dp[i][target]= dp(i+1,target-nums[i]) or dp(i+1,target)
            return self.dp[i][target]
        totalsum = sum(nums)
        if(totalsum%2): return False 
        else: 
            self.dp = [ [-1]*((totalsum//2)+1) for _ in range(len(nums))]
            return dp(0,totalsum//2)

[NorthSeacoder]

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
    const sum = nums.reduce((acc, cur) => acc + cur, 0);
    if (sum % 2 !== 0) return false;
    const target = sum / 2;
    const size = nums.length;
    const dp = new Array(size + 1).fill().map(() => new Array(target + 1).fill(0));
    //dp[i][j] 表示[0-i]范围内,容量为 j 的情况下,和的最大值(不能超过 j)
    //初始化,当 j>=nums[0]时dp[0][j]=nums[0];dp[i][0]=0
    for (let j = nums[0]; j <= target; j++) {
        dp[0][j] = nums[0];
    }
    for (let i = 1; i < size;i++) {
        //遍历物品
        for (let j = 0; j <= target; j++) {
            //遍历背包
            if (j < nums[i]) {
                //不能取nums[i]
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
            }
        }
    }
    return dp[size-1][target] ===target
};

[RestlessBreeze]

code

class Solution {
public:
    bool canPartition(vector<int>& nums) {

        int sum = 0;
        for (int i = 0; i < nums.size(); i++)
            sum += nums[i];
        if (sum % 2 != 0)
            return false;
        int target = sum / 2;
        vector<int> dp(target + 1);
        for (int i = 0; i < nums.size(); i++)
        {
            for (int j = target; j >= nums[i]; j--)
            {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[target] == target ? true : false; 
    }
};

[lp1506947671]

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]

[LIMBO42]

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // 背包问题，问能不能是一般
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % 2 == 1) return false;
        sum /= 2;
        // 问能不能求
        vector<vector<bool>> dp(nums.size() + 1, vector<bool>(sum + 1, false));
        // dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i-1]]
        dp[0][0] = true;
        for(int i = 1; i <= nums.size(); ++i) {
            for(int j = 1; j <= sum; ++j) {
                if(j >= nums[i-1]) {
                    dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i-1]];
                } else {
                    dp[i][j] = dp[i-1][j];
               }
            }
        }
        return dp[nums.size()][sum];
    }
};

[Meisgithub]

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for (const int& num : nums)
        {
            sum += num;
        }
        if (sum & 1)
        {
            return false;
        }
        sum /= 2;
        vector<vector<int>> dp(n + 1, vector<int>(sum + 1, 0));
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 0; j <= sum; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1])
                dp[i][j] |= dp[i - 1][j - nums[i - 1]];
            }
        }
        return dp[n][sum];
    }
};

[wangzh0114]

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;
        for (auto& num : nums) {
            sum += num;
            maxNum = max(maxNum, num);
        }
        if (sum & 1) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        vector<int> dp(target + 1, 0);
        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];
    }
};

[Size-of]

/**

• @param {number[]} nums
• @return {boolean} */ 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(n).fill(0).map(() => new Array(target + 1, false)); for (let i = 0; i < n; i++) { 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]; };

[harperz24]

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)

        if total % 2 == 1:
            return False

        subtotal = total // 2
        n = len(nums)

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

        for num in nums:
            for j in range(subtotal, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]

        return dp[subtotal]

        # knapsack 
        # time: O(m * n)
        # space: O(m)

[DragonFCL]

var canPartition = function (nums) {
  var sum = nums.reduce((a, b) => a + b);
  if (sum % 2 === 1) return false;
  let bgSize = sum / 2; // 两个子集的和
  let len = nums.length;
  let dp = new Array(bgSize + 1).fill(0); // dp初始化
  // 先遍历物品
  for (let i = 0; i < len; i++) {
    for (let j = bgSize; j >= nums[i]; j--) {
      dp[j] = Math.max(
        dp[j], // 不放改物品
        dp[j - nums[i]] + nums[i], // 放物品
      );
    }
  }
  return dp[bgSize] === bgSize;
};

[Jetery]

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int len = nums.size();
        int sum = 0;
        for (int e : nums) sum += e;
        if (sum & 1 == 1) return false;
        int target = sum >> 1;
        vector<vector<bool>> dp(len, vector<bool>(target + 1, false));
        if (nums[0] <= target) dp[0][nums[0]] = true;
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < target + 1; j++) {
                dp[i][j] = dp[i - 1][j];
                if (nums[i] == j) {
                    dp[i][j] = true;
                    continue;
                } else if (nums[i] < j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[len - 1][target];
    }
};

[aoxiangw]

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2:
            return False
        dp = set()
        dp.add(0)
        target = sum(nums) // 2
        for i in range(len(nums) - 1, -1, -1):
            nextDP = set()
            for t in dp:
                if (t + nums[i]) == target:
                    return True
                nextDP.add(t + nums[i])
                nextDP.add(t)
            dp = nextDP
        return True if target in dp else False

[Diana21170648]

思路

动态规划，背包问题，也可用dfs求解

class Slution:
    def equalsubsetsum(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]

**复杂度分析**
- 时间复杂度：O(m*n)
- 空间复杂度：O(n)

[kangliqi1]

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]

[bookyue]

TC: O(n^2)
SC: O(n^2)

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;

        if ((sum & 1) == 1) return false;

        return dfs(nums, sum / 2, 0, new Boolean[nums.length][sum / 2 + 1]);
    }

    private boolean dfs(int[] nums, int sum, int idx, Boolean[][] dp) {
        if (idx == nums.length || sum < 0) return false;

        if (dp[idx][sum] != null) return dp[idx][sum];

        if (sum == 0) return dp[idx][sum] = true;

        for (int i = idx; i < nums.length; i++) {
            if (dfs(nums, sum - nums[i], i + 1, dp))
                return dp[i][sum] = true;

            dp[i][sum] = false;
        }

        return dp[idx][sum] = false;
    }

[JasonQiu]

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if len(nums) == 0:
            return False
        s = sum(nums)
        if s & 1 == 1:
            return False
        target = s // 2
        dp = [False for _ in range(target + 1)]
        for j in range(target + 1):
            if nums[0] == j:
                dp[j] = True
                break
        for i in range(1, len(nums)):
            for j in range(target, -1, -1):
                if j < nums[i]:
                    break
                dp[j] = dp[j] or dp[j - nums[i]]
        return dp[-1]

Time: O(n*sum/2) Space: O(sum/2)

[X1AOX1A]

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]

[snmyj]

class Solution {
public:
    bool canPartition(vector<int>& nums)
    {
        int SUM = accumulate(nums.begin(), nums.end(), 0);
        int Size = SUM / 2;
        vector<vector<int>> dp(nums.size(), vector<int>(Size + 1, 0));
        if (SUM % 2 == 1) return false;
        sort(nums.begin(),nums.end());
        //初始化 
        for (int j = 0; j <= Size; j++)
        {
            if (j >= nums[0])  dp[0][j] = nums[0];
        }

        for (int i = 1; i < nums.size(); i++)
        {
            for (int j = Size; j >0; j--)
            {
                if (j < nums[i])  dp[i][j] = dp[i - 1][j];
                else  dp[i][j] = max(dp[i - 1][j], dp[i-1][j - nums[i]] + nums[i]);
            }
        }
        if(dp[nums.size()-1][Size]!=Size)
            return false;
        return true;
    }
};

[FireHaoSky]

思路：动态规划

代码：python

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 2:
            return False
        total = sum(nums)
        if total % 2 != 0:
            return False

        target = total // 2
        dp = [True] + [False] * target
        for i, num in enumerate(nums):
            for j in range(target, num - 1, -1):
                dp[j] |= dp[j - num]
        return dp[target]

复杂度分析：

"""
时间复杂度：O(n*target)
空间复杂度：O(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];
    }
}

复杂度分析

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

[yingchehu]

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]

[Lydia61]

416. 分割等和子集

思路

0-1背包问题

代码

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 2:
            return False

        total = sum(nums)
        if total % 2 != 0:
            return False

        target = total // 2
        dp = [True] + [False] * target
        for i, num in enumerate(nums):
            for j in range(target, num - 1, -1):
                dp[j] |= dp[j - num]

        return dp[target]

复杂度分析

• 时间复杂度：O(mn)
• 空间复杂度：O(n)

[joemonkeylee]

思路

dp

代码

        public int Rob(int[] nums)
        {
            if(nums.Sum() % 2 != 0) return false;

            int sum = nums.Sum()/2;
            int[] dp = new int[10001];
            dp[0] = 0;

            for(int i = 0; i < nums.Length; i++){
                for(int j = sum; j >= nums[i]; j--)
                    dp[j] = Math.Max(dp[j], dp[j - nums[i]] + nums[i]);
            }
            return dp[sum] == sum;

        }

复杂度分析

• 时间复杂度：O(n*target) target 是整个数组的元素和的一半
• 空间复杂度：O(target)

[kofzhang]

思路

动态规划，01背包问题

复杂度

时间复杂度：O(mn) 空间复杂度：O(n)

代码

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 2:
            return False

        total = sum(nums)
        if total % 2 != 0:
            return False

        target = total // 2
        dp = [True] + [False] * target
        for i, num in enumerate(nums):
            for j in range(target, num - 1, -1):
                dp[j] |= dp[j - num]

        return dp[target]

[chanceyliu]

代码

function canPartition(nums: number[]): boolean {
  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];
    }
  }
  return dp[target];
}

[Zoeyzyzyzy]

class Solution {
    // 求出集合中是否存在和为sum/2的子集
    // 可以将其转化为0-1背包问题，相当于有一堆物品重量为num[i],价值为nums[i] 看能否恰好装满容量为sum / 2的背包
    // dp[j]: 容量为j的背包，所背物品的最大价值为dp[j]
    // 递推公式： dp[j] = max(dp[j],dp[j - nums[i]] + nums[i])
    // 初始化：让dp数组在递推的过程中取得最大的价值，而不是被初始值覆盖了, dp[0] = 0
    // 遍历顺序： 物品遍历for在外围，正序遍历， 背包倒序遍历。 
    // 最后需要判断 dp[sum / 2] ?= sum /2 即可
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (sum % 2 != 0)
            return false;
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }
}