目录

0416:分割等和子集(★)

力扣第 416 题

题目

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

示例 1:

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

示例 2:

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

提示:

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

相似问题:

分析

#1

  • 令 s 为数组的和,问题相当于找子集满足和等于 s/2
  • 这可以看作背包问题,递推即可
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        if s%2:
            return False
        s //= 2
        f = [1]+[0]*s
        for x in nums:
            for i in range(s,x-1,-1):
                f[i] |= f[i-x]
        return bool(f[-1])

785 ms

#2

  • 由于递推时只关心 f 值为 1 的元素,所以可以直接用 set 维护
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        if s%2:
            return False
        s //= 2
        vis = set()
        for x in nums:
            vis |= {y+x for y in vis|{0} if y+x<=s}
        return s in vis

534 ms

#2

  • 由于 vis 集合的递推只涉及到加法,所以可以用二进制优化
  • 用二进制状态 st 表示 vis 集合,集合内所有数加上 x 即是 st « x

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        if s%2:
            return False
        s //= 2
        st = 0
        for x in nums:
            st |= (st|1)<<x
        return bool(st&1<<s)

37 ms